超图的结构性质及相关参数研究

The studies in the structure problems of hypergraph are growing very fast in the recent years. Many research problems are even directly from computer science, communication technology and management science. This project studies the following scientific problems in the structural properties of hypergraph by effectively using and integrating the mathematical methods in Algebra and Optimization Theory. The relationship between some hypergraph parameters and eigenvalues of hypergraph (such as the adjacent tensors, the Laplacian tensors, the signless Laplacian tensors) will be deeply investigated; the structural properties of hypergraph, especially the matching problems and the partition problems will be studied and hopefully some novel methodology for hypergraph will be obtained based on our longtime research experience in structural and extremal Graph Theory; computational methods for the problems listed above and their complexity analysis will also be addressed in this project.

超图的结构问题是图论研究的热点，许多研究问题直接来自计算机科学、通讯、运筹和管理等实际应用领域。本项目拟结合代数、数学规划等方法，通过对超图结构性质的研究，进一步深入的探索超图的邻接张量、拉普拉斯张量及无符号拉普拉斯张量谱半径的极值和极图，研究超图三种张量特征值与超图某些参数之间的关系；在我们长期从事结构图论、极值图论研究的基础上，对超图的结构性质进行研究，重点研究超图的匹配问题和超图的划分，基于我们在结构图论方面的研究积累，为研究这类问题探索一些新的方法；与科学计算方法相结合，探讨超图的某些结构在算法上的实现并研究算法的复杂性。

通过探索超图的结构性质以及超图的结构与各种参数之间的内在联系，充分利用图论、代数、数论、数学规划等数学知识，我们对超图的若干参数的极值及参数之间的关系、超图的匹配问题和超图划分问题进行了研究，取得的成果主要包括：（1）利用Ore型条件，给出了3-一致超图中存在d-匹配和完美匹配的Ore型充要条件及充分条件，我们的度条件在某种情况下是紧的。（2）证明了完全平衡(k+1)-部k-一致超图具有完美匹配及哈密尔顿紧圈分解；完全平衡(k+2)-部k-一致超图具有完美匹配分解。（3）给出了图的各类拓扑参数的上、下界，并刻划了达到这些界的极图；否定了Hansen 和Lucas在2010年提出的有关无符号Laplacian谱半径与独立数关系的猜想；给出一个新的图矩阵并研究其相关性质；利用新方法研究反Ramsey数。（4）给出了超图的树宽定义及线性超图2-截口树宽的上下界，为超图中NP-完全问题的算法设计提供了理论依据；给出树宽有界图两类NP-完全问题的参数化算法。..依托本项目，我们已发表SCI检索的学术论文23篇，培养博士研究生4名，硕士研究生2名，在站博士后1名，在读博士研究生8名.