Essential independent sets and Hamiltonian cycles

An independent set S of a graph G is said to be essential if S has a pair of vertices distance two apart in G. We prove that if every essential independent set S of order k ≥ 2 in a k-connected graph of order p satisfies max {deg v:v ϵ S} ≥ ½ p, then g is hamiltonian. This generalizes the result of Fan (J. Combinatorial Theory B 37 (1984), 221–227). If we consider the essential independent sets of order k + 1 instead of k in the assumption of the above statement, we can no longer assure the existence a hamiltonian cycle. However, we can still give a lower bound to the length of a longest cycle. © 1996 John Wiley & Sons, Inc.