LIU Yiping;TIAN Feng;WU Zhengsheng
Journal of Systems Science and Complexity. 1995, 8(2): 144-151.
Let G be a simple finite graph, I_{k+1} (G) the set of independent sets of cardinality (k + 1) of G. If Y ∈I_{k+1}(G), define S_i(Y)={v|N(v)\cap Y| = i}, s_i(Y) =|S_i(Y)|for each i ∈ {0, 1, 2,...,k+1}. In this paper we prove that, if k ≥ 2 and G is a k-connected graph of order n such that Σ_{i=1}~k {k+i-2}/{k-1}s_i(Y) + 2s_{k+1}(Y) > n - 1 for each Y ∈ I_{k+1}(G),then G is hamiltonian. This theorem generalizes several well-known sufficient conditions for graphs to be hamiltonian.