图中参数与子图存在性问题研究

The subgraph existence problem is a hot topic in the research of Graph Theory. It not only has important theoretical significance, but also enjoys strong applicability in theoretical computer science, biological science, management science and information science. Proceeding from several basic parameters of graphs including independence number, minimum degree and bipartite binding number, this project is intended to make a deep research on some subgraph existence problems such as the cycle structures of bipartite graphs and the existence of spanning trees with few branch vertices or few leaves. By introducing some new methods and techniques such as the nested cycle structures and the art of inserting edges and exploring the Bipartite Hopping Lemma, we will investigate the circumference, the hamiltonicity and the bipancyclism of bipartite graphs; and by combining some overall properties and partial properties of graphs and applying the latest methods and techniques in the research of the structures of special spanning trees, we will further explore the relationship between the existence of spanning trees with few branch vertices or few leaves and some basic parameters of graphs including independence number, connectivity and degree sum. As a result, the project will contribute to the earlier solution to the Hoggkvist conjecture on the hamiltonicity of 2-coonected k-regular bipartite graphs, which will help to elevate the research on graph structure theory in China to the international level.

图中子图存在性问题是图论研究的一个热点，对其进行研究不但有重大的理论意义，而且在理论计算机科学、生命科学、管理科学和信息科学中有很强的应用背景。本项目拟从独立数、最小度、两分结合数等图中基本参数出发,对图中特定子图的存在性问题进行深入探讨，研究内容包括二部图的圈结构和图中特型支撑树的存在性两个方面。我们将通过引入一些新的圈套结构和二部图的"插边"技巧，并利用Hopping 引理等工具，对二部图的周长、哈密尔顿性和偶泛圈性进行研究；将图的整体性质与局部性质相结合，并利用图中特型支撑树研究的最新方法和技巧,试图深入探讨图中具较少分枝点和具较少悬挂点的支撑树的存在性与独立数、连通度以及度和等图中基本参数之间的关系。本项目的研究将推进Hoggkvist关于2-连通图 k-正则二部图的哈密尔顿性猜想的早日解决，有利于我国图论研究与世界进一步接轨。

子图存在性问题是图论研究的一个热点。本项目利用连通度、最小度等图中基本参数，对子图存在性问题进行了深入探讨，在图中过特定点集的最长圈、 二部图的圈结构、图中特型支撑树的存在性、3-连通无爪图的哈密尔顿性、图谱以及图中结构的代数特征等方面取得重要进展, 共发表研究论文30篇，其中27篇被SCI收录。主要结果如下：(1)对图中过特定点集的最长圈问题进行了卓有成效的探讨， 使Locke和Zhang 于1991年提出的一个公开问题取得重要进展，相关论文在Journal of Graph Theory 87(2018) 374-393上发表； (2) 对二部图的最小度与其弱偶泛圈性、以及哈密尔顿二部图的最小度与其偶泛圈性之间的关系进行了深入探讨，证明了所有最小度至少为n/3+4的2n阶哈密尔顿二部图都是偶泛圈图，相关论文Discrete Applied Mathematics 194(2015)102-120发表；(3)对图中特型支撑树的存在性进行了卓有成效的研究，相关论文分别在Journal of Graph Theory 77(2014) 237–250和Science China Mathematics 57(2014)1579-1586发表； (4) 对无爪图的哈密尔顿性与连通度、禁用子图的关系进行了探讨，发表SCI论文两篇，其中之一证明了所有3-连通{K_{1,3}, N_{1,2,3}}-free 图都是哈密尔顿连通图；(5) 对图的各类谱和图中结构的其它几类代数特征进行了深入探讨， 在 Discrete Applied Mathematics, Graphs and Combinatorics, Linear Algebra and Its Applications等SCI期刊发表论文18篇。本项目的研究拓展了子图存在性问题研究的内涵，有利于我国图论研究与世界进一步接轨。