Essential independent sets and long cycles (Q1613438)

An essential independent set is an independent set which has a pair of vertices that are distance two apart. For \(S\subset V(G)\) with \(S\not= \emptyset\), let \(\Delta(S)=\max\{d_G(x)\mid x\in S\}\). The following theorem is proved. Let \(k\geq 2\) and let \(G\) be a \(k\)-connected graph. Suppose that \(\Delta(S)\geq d\) for every essential independent set \(S\) of order \(k\). Then \(G\) has a cycle of length at least \(\min\{|G|,2d\}\). This result is sharp in the following sense. Let \(p\geq d\geq k\) and let \(G=K_d+pK_1\), where the plus sign denotes join. Then it is easy to see that \(G\) is \(k\)-connected and \(\Delta(S)\geq d\) for every essential independent set \(S\) of order \(k\). On the other hand, the length of a longest cycle in \(G\) is \(2d\).