超图的横贯、控制集和匹配研究

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. The domination in graphs is a branch of graph theory that has developed very rapidly. The project studies transversals, dominating sets, matchings in hypergraphs and relationships between them. Ryser’s conjecture, Jones conjecture and Henning-Yeo’s conjecture are closely related to transversal, domination, matching numbers in hypergraphs. Our aim is to prove the three conjectures. According to the structural properties of hypergraphs, we investigates the transversal, domination and matching numbers by using combination, probability and linear programming methods, the technique of conversion between hypergraphs and graphs, and the relationships between domination parameters and coloring of hypergraphs. We shall provide bounds on transversal, total transversal, domination and total domination numbers 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猜想、Jones猜想和Henning-Yeo猜想是涉及超图的横贯数、匹配数和全控制数之间关系的三个重要猜想。本项目将以这几个猜想为研究目标。从超图的结构特点出发，借助超图与图之间的相互转换，利用超图的控制参数与超图染色之间的关系，运用组合、概率和线性规划等方法，给出超图的横贯数、全横贯数、控制数和全控制数的界，确定这些参数之间的内在联系，刻画相应的极值超图，并分析这些问题在特殊超图类上的计算复杂性。力争在这几个猜想上取得实质性突破。本项目的研究对推动超图理论发展和在相关领域的应用具有重要意义。

超图理论在通讯网络，计算机科学，张量理论和博弈论等领域具有广泛的应用，近年来成为图论和组合研究的重要内容之一。本课题对超图的控制集、横贯、匹配和谱理论进行了研究，涉及超图中的Ryser猜想等重要问题。证明了秩为r的超图其控制数不超过它匹配数的(r-1)倍。作为推论，证明了当超图的控制数和横贯数相等时，Ryser猜想是成立的。对秩不超图5的极值超图给出了刻画。证明了每个一致的无桥偶度超图一定存在圈分解，而且每个无桥超图存在总长度至多为边数与点数之和减1的圈覆盖。建立了p-部超图为极大点连通和极大边连通的充分条件。这些结论推广了文献中关于图上的相关结论。证明了最大1-边临界超图和最大1-点临界超图具有相同的阶数。2016年， Katona和Szabo证明了n阶k-一致超树的最大边数上界，并猜想这个上界是最好可能的，本课题证明了这个猜想是成立的。此外，给出了超树的匹配多项式的表达式，以此作为工具，对给定直径和边数的超树，对具有较大谱半径的和较小的两个谱半径的超树给出了刻画。建立了一致超图的α-谱半径按照控制数的下界，并刻画了达到界的极值超图。给出了超图的邻接张量、Laplacian张量和无符号Laplacian张量的谱半径的界，这些结论推广了原来在图上的相关结论。研究了超图与合作博弈的交叉研究领域，并取得一些突破性进展，给出了以超图结构为合作结构的合作博弈的几个重要分配规则，并对这些分配规则给出了公理化刻画。