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

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).

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

图的哈密尔顿性是结构图论研究中的一个传统而经典的课题。该课题与四色问题、极值问题、图的结构理论问题有着紧密的联系，并且它在信息科学、生物科学、分子化学等学科也有着重要应用。由于哈密尔顿问题是一个NP-完全问题，因此，众多学者把研究哈密尔顿问题的目光转移到了寻找图中存在哈密尔顿圈的充分条件上。在哈密尔顿圈存在的众多充分条件中，度条件和禁止子图条件是两类重要条件。由于这些条件都是充分条件，因此，不断弱化、推广这些充分条件尤为必要。本项目主要是在隐度条件下研究了图的哈密尔顿问题。首先，给出了计算图中所有顶点的隐度的一个多项式算法，此算法相对于哈密尔顿问题是一个NP-完全问题来说，是一个非常好的算法。其次，我们通过考虑图的隐度给出了k-连通图是哈密尔顿的一个充分条件。在项目执行期间，我们发现将隐度限制在图的某些特殊结构上来研究图的哈密尔顿性是一个新颖且有意义的课题。并且沿着这一方向我们得到了两个比较理想的结果，分别给出了2-隐重图是哈密尔顿的一个充分条件以及在禁止子图下给出了爪隐重图是哈密尔顿的一个充分条件。. 隐度条件下图的哈密尔顿问题研究是一个较新的课题，成果还不丰富。然而由隐度的定义可以看出一个顶点的隐度不小于该顶点的度。因此在隐度条件下研究图的哈密尔顿性可以弱化、推广哈密尔顿圈存在的充分条件，这对图的哈密尔顿理论研究具有积极的促进作用。