一致超图结构性质研究

Hypergraph structural theory is a generalization of graph structural theory, which not only plays an important role in basic subjects such as graph theory, combinatorics, but also has a wide application in industrial production and people’s life. Perfect matching and Hamilton cycle are two important structures of hypergraph, whose existence problem has received much attention in recent years. International scholars mainly study the existence problem for perfect matching from Dirac-condition and the number of edges and the existence problem for Hamilton cycle from Dirac-condition. Applicant plans to consider the existence problem for perfect matching and Hamilton cycle from Ore-condition. We hope to achieve some breakthroughs on the problem by trying some new methods, such as switching method. It is expected that substantial progress can be made in the study of the relationship between hypergraph matching and Hamilton cycle and the Ore-condition. The results of the study are provided in the form of papers. We plan to publish at least three SCI papers.

超图结构理论是图结构理论的深化与推广，不仅在图论，组合学等基础学科中有重要的地位，而且在现实世界人们的生产生活中也有十分广泛的应用。超图（完美）匹配，哈密顿圈是超图非常重要的两个子结构，其存在性问题受到国际国内专家学者的密切关注和研究，当前国内外学者主要从Dirac-型条件和边数两个角度研究超图匹配的存在性，从Dirac-型条件研究超图哈密顿圈的存在性。本项目拟通过对超图的结构性质进行研究，试图将Ore-型条件引用到超图(完美)匹配和哈密顿圈存在性问题的研究中；申请人欲探索一些新的方法，如换点方法等，希望在对超图(完美)匹配和哈密顿圈存在性问题的理论研究方法方面能得到一些新的突破。预期可在超图匹配及哈密顿圈存在性与 Ore-型条件之间关系的研究上取得实质性的进展，其研究成果以论文形式提供，计划完成SCI检索论文至少3篇。

超图（完美）匹配和哈密顿圈是超图中非常重要的两个子结构，研究完美匹配和哈密尔顿圈的存在性问题在理论和应用上都有非常重要的应用，受到国际国内学者的密切关注。国际上主要从Dirac条件和边条件两个角度研究完美匹配的存在性，Ore条件也是确保图存在某一种特定结构的重要条件，在本项目中，我们主要从Ore条件出发，研究3一致超图匹配的存在性. 我们找到了确保3一致超图存在大小为s的匹配的Ore条件下的极值图. 该极值图与Dirac极值图和边数极值图都不同，我们分两篇文章证明了当一个3一致超图的两个相邻顶点的最小度和大于Ore极值图的两个相邻顶点的最小度和时，其一定存在一个大小为s的匹配。这两篇论文都发表在Electronic Journal of Combinatorics上. 因为Ore极值图的两个相邻顶点的最小度和比Dirac极值图的两个相邻顶点的最小度和大，我们原本猜测如果一个3一致超图的两个相邻顶点的最小度和大于Dirac极值图的两个相邻顶点的最小度和，则该超图或者存在大小为s的匹配或者是Ore极值图的子图. 当我们在研究完美匹配的时候，我们发现一个反例，该反例是Dirac极值图和Ore极值图相结合的新的极值图. 最近我们正在尝试证明如果一个3一致超图的两个相邻顶点的最小度和大于新极值图的两个相邻顶点的最小度和，则其或者包含一个完美匹配或者是Ore极值图的子图. 另一方面，国际上很多学者研究超图的分解问题，两个方向：1 高对称图形的分解问题，比如n个顶点的完全图就是一个高对称图；2 从最小度的角度给出分解的充分条件. 我们研究了高对称超图，完全n平衡，k+1部，k一致超图的完美匹配和哈密尔顿圈分解问题. 我们证明了完全n平衡，k+1部，k一致超图存在哈密尔顿紧圈分解; 完美匹配分解的必要条件也是充分条件. 先后在Applied Mathematics and Computation和SIAM Discrete Mathematics上发表了两篇论文.