隐度条件下图的哈密尔顿圈

项目名称： 隐度条件下图的哈密尔顿圈

项目编号： No.11426145

项目类型： 专项基金项目

立项/批准年度： 2015

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

项目作者： 蔡俊青

作者单位： 曲阜师范大学

项目金额： 3万元

中文摘要： 哈密尔顿问题是图论研究中的一个传统而经典的问题。它在信息科学、生物科学和分子化学等方面有着广泛应用。由于哈密尔顿问题是一个NP-完全问题，因此，众多学者致力于研究哈密尔顿问题的充分条件，并产生了诸多经典结果。在这些经典结果中顶点的度条件是一个非常重要的指标。但是存在不满足已有的度条件的哈密尔顿图，因此不断弱化、推广这些已有的充分条件尤为必要。本项目致力于在新的指标-“隐度”下深化和推广图的哈密尔顿问题的一些经典结果。一方面，在隐度条件下寻找图中存在哈密尔顿圈、最长圈的充分条件；另一方面，根据Bondy的meta-猜想（几乎所有能表明一个图是哈密尔顿的非平凡条件，都可以表明这个图是泛圈的（可能除了一些特殊图类外）。），在隐度条件下研究图的泛圈性。

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

英文摘要： Hamilton problem is a traditional and classic problem in graph theory. It has extensive applications in Information, Biological and Molecular Chemistry etc. Since Hamilton problem is an NP-complete problem, many scholars work on studying the sufficient conditions for the existence of Hamilton cycles and get many classical results. Among these conditions, the degree of a vertex is an important index. But there exists Hamilton graphs not satisfying these conditions, so it is necessary to weaken and extend these conditions. In the subject, we devote to deepen and extend these classical results under a newer index “implicit degree”. Firstly, we will look for sufficient conditions under implicit degree conditions for the existence of Hamilton 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 a special family of graphs).

英文关键词： Hamilton cycle；Pancycle；Implicit degree；Forbidden subgraphs；