隐重子图条件下图的圈

In 1984, the famous graph theorists Matthews and Sumner conjectured that every 4-connected claw-free graph is hamiltonian. Nowdays, the conjecture is still open and many related problems have been posed by reseachers. In 1997, Broersma et.al had obtained a sufficient condition for the existence of hamiltonian cycles by imposing “degree condition” on some special structures. Since there exist hamiltonian graphs not satisfying known conditions, it is necessary to weaken and extend those known conditions. In this subject, we devote to deepen and extend these classical results under a new index “implicit degree”. Firstly, we will look for sufficient conditions by imposing implicit degree conditions on some special structures for the existence of hamiltonian cycles. Secondly, we will study the pancyclicity of graphs under implicit degree conditions according to Bondy's meta-conjecture that almost any nontrivial condition which implies that a graph is hamiltonian also implies that the graph is pancyclic (except maybe for some special families of graphs.

1984年，著名图论学者 Matthews 和 Sumner 提出猜想“4-连通无爪图是哈密尔顿”。此猜想至今尚未被解决且由此引申出诸多研究课题，如特定条件下研究2-连通无爪图的哈密尔顿性。1997年，Broersma 等人将度条件和禁止子图条件结合起来，得到了图是哈密尔顿的一个充分条件。由于存在不满足已有度条件的哈密尔顿图，因此不断弱化、推广已有条件尤为必要。本项目旨在新的指标“隐度”下深化和推广哈密尔顿问题的一些经典结果。一方面将隐度限制在图的某些特殊结构上以寻找图中存在哈密尔顿圈的充分条件；另一方面，根据 Bondy的 meta-猜想“几乎所有使得图是哈密尔顿的非平凡条件都能保证该图是泛圈的（可能除了某些特殊图类外）”，在图中存在哈密尔顿圈的条件下进一步研究图的泛圈性。

本课题主要研究了隐重子图条件下图的圈结构问题。研究了2-连通图中存在哈密尔顿圈的隐重子图条件和禁止子图条件；研究了隐度条件下图的最长圈问题和支撑树的叶子数问题；在图中存在哈密尔顿圈的条件下进一步研究了图的泛圈性。. 哈密尔顿圈方面：在禁止子图条件下研究了2-连通2-隐重图中哈密尔顿圈的存在性；在三类禁止子图条件下研究了2-连通爪隐重图的哈密尔顿性；将隐度限制在图的基本独立集上研究了k-连通2-重图的哈密尔顿性；将隐度限制在图的三类特殊子图上研究了2-连通爪隐重图的哈密尔顿性；在2-基本控制集的条件下研究了2-连通爪重图的哈密尔顿性；在局部Ore-型隐度条件下研究了k-连通图的哈密尔顿性。. 最长圈方面：通过考虑3个非相邻顶点的最小隐度和，研究了2-连通图的最长路与最长圈的相对长度问题；通过考虑4个非相邻顶点的度和加上其邻域并中的顶点数减去其邻域交的顶点数的最小值，研究了4-连通图中最长圈的长度问题；通过考虑顶点数为k(G)+1 的独立集中任意两个顶点的最大隐度和与图的顶点数之间的关系，研究了2-连通图中最长圈的长度问题。. 支撑树方面：研究了隐度条件下连通图中支撑树的叶子数的上界问题；在隐度和条件下研究了K1,4-free 连通图中支撑树的叶子树；在度和条件下研究了K1,5-free 连通图中支撑树的叶子数。. 泛圈性方面：根据 Bondy 给出的meta-猜想：几乎所有能表明一个图是哈密尔顿的非平凡条件，都可以表明这个图是泛圈的（可能除了一些特殊图类外），在哈密尔顿圈存在的条件下进一步研究图的泛圈性。将隐度限制在两类禁止子图条件下研究图的泛圈性；将度条件限制在两类特殊子图上研究2-连通图的弦泛圈。由于隐度联系了顶点的邻点以及距离为2的顶点的度，所以在研究中不会像传统的度那样直观。目前我们还没有得到泛圈性方面比较理想的结果，这将是我们下一步努力的方向。. 在本课题的资助下，共发表论文9篇，其中SCI论文8篇，英文期刊论文1篇，培养了硕士研究生5名。