隐重子图条件下图的圈

项目名称： 隐重子图条件下图的圈

项目编号： No.11501322

项目类型： 青年科学基金项目

立项/批准年度： 2016

项目学科： 数理科学和化学

项目作者： 蔡俊青

作者单位： 曲阜师范大学

项目金额： 18万元

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

中文关键词： 哈密尔顿圈；隐度；隐重子图；泛圈性

英文摘要： 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.

英文关键词： Hamiltonian cycle;Implicit degree;Implicit-heavy subgraph;Pancyclicity