k-连通图中存在哈密尔顿圈的一个隐度条件

An implicit degree condition for hamiltonian cycles in k-connected graphs

文中给出了强基本独立集的概念,并证明了如下定理:设G是一个具有n个顶点的k-连通图,其中k≥2.如果对任意一个具有k个顶点的强基本独立集S,都有max{d1(x)|x∈S}≥n/2,则G是哈密尔顿图.此定理推广了已有的几个有关图中哈密尔顿圈存在性的定理.

This paper gives a new concept of strong essential independent set, and proves the following theorem： Let k 〉 2 and let G be a k-connected graph on n vertices such that max{d1 （x） ｜ x∈ S} ≥n/ 2 for every strong essential independent set S on k vertices. Then G is hamiltonian.