超图的横贯和控制集的研究

Hypergraphs have gradually become a hot topic in graph theory and combinatorial theory since the advent of Berge monograph on hypergraphs in 1989. Hypergraphs can model more general types of relations than graphs do. It can be used to model communication networks, biology networks, data structures, tensor and a variety of other systems where complex relationships between the objects in the system. Traversal is the important content of graph theory, the domination in graphs is a branch of graph theory that has developed very rapidly. The project studies dominating sets and transversals in hypergraphs and relationships between them. Ryser’s conjecture and Henning-Yeo’s conjecture are closely related to transversal, domination, matching numbers in hypergraphs. Our aim is to prove the two conjectures. According to the structural properties of hypergraphs, we investigates the transversal, domination and matching numbers by using combination, probability methods, the technique of conversion between hypergraphs and graphs. We shall provide bounds on domination and total domination numbers, transversal and total transversal of hypergraphs, and determine the inequality relationships between these parameters. Also, we shall characterize extremal hypergraphs with equal parameters, and present the computational complexity on corresponding problems in the special class of hypergraphs. The research of this project play a major role in promoting hypergraph theory and application to the related fields.

自从1989年Berge关于超图的专著问世以来，超图逐渐成为图论与组合研究的热点问题，这是因为超图在理论上更具有一般意义，同时它在通讯网络、生物网络、数据结构、张量以及各种复杂系统中具有广泛的应用。而横贯是图论研究的重要内容之一，图的控制集是图论发展最快的领域之一。本项目研究超图的控制集和横贯以及它们之间的关系。Ryser猜想和Henning-Yeo猜想是涉及超图的横贯数、匹配数和全控制数之间关系的三个重要猜想。本项目将以这几个猜想为研究目标。从超图的结构特点出发，借助超图与图之间的相互转换，运用组合、概率等方法，给出超图的控制数和全控制数、横贯数和全横贯数的界，确定这些参数之间的内在联系，刻画相应的极值超图，并分析这些问题在特殊超图类上的计算复杂性，力争在这两个猜想上取得实质性突破。本项目的研究对推动超图理论发展和在相关领域的应用具有重要意义。

超图的横贯、匹配和染色是超图的经典概念。最近，对超图控制集的研究也开始活跃起来。本项目研究超图的横贯、控制集以及它们之间的关系，旨在解决其中的一些重要问题，并在相关猜想的研究上取得进一步地进展。这些问题的解决对于深刻认识超图的结构性质具有重要的理论意义。同时，为推进超图在通讯、大数据挖掘、图像处理和张量理论等领域中的应用提出强有力的理论支撑。. 本课题项目的研究是从超图的几个重要猜想： Ryser 猜想、Tuza 猜想和 Henning-Yeo 猜想出发，通过分析和利用超图的结构性质，结合概率方法，给出超图的横贯、和控制数的界的估计，研究这些参数之间的内在关系以及它们与匹配数之间的关系，并刻画相应的各种极值图类。具体研究内容和关键问题如下：.1.超图的控制集与匹配，特别是某类特殊超图；.2.超图的控制数与匹配数关系及其极值超图研究；.3.超图的横贯和控制集的研究和特殊图上的控制集问题.. 我们针对上述的猜想和几个问题，进行学习和研究，我们试图解决部分猜想和问题。结合我们提出的研究内容和欲解决的关键问题, 针对超图和图的结构特点，利用超图和图相结合及相互转化方法，组合方法、概率方法以及组合优化方法等进行研究。课题组首先主要研究了幂超图，广义幂超图和交超图的控制集和匹配的关系，以及极值图的刻画等内容；其次讨论了有向图的k-元控制集；最后，为进一步地探讨，拓展，学习和研究超图理论的应用，我们对于在合作博弈和团染色方面进行了初步探讨。