Essential independent sets and long cycles Original Research Article

An independent set S of a graph G is said to be essential if S has a pair of vertices that are distance two apart in G. For S⊂V(G) with S≠∅, let Δ(S)=max{dG(x)|x∈S}. We prove the following theorem. Let k⩾2 and let G be a k-connected graph. Suppose that Δ(S)⩾d for every essential independent set S of order k. Then G has a cycle of length at least min{|G|,2d}. This generalizes a result of Fan.