A Local Neighbourhood Condition for Cycles

Let \(G\) be a connected graph with \(v \geq 3\). Let \(v \in V(G)\). We define \(N_k(v) = \{u|u \in V(G) \text{ and } d(u,v) = k\}\). It is proved that if for each vertex \(v \in V(G)\) and for each independent set \(S \subseteq N_2(v)\), \(|N(S) \cap N(v)| \geq |S| + 1\), then \(G\) is hamiltonian. Several previously known sufficient conditions for hamiltonian graphs follow as corollaries. It is also proved that if for each vertex \(v \in V(G)\) and for each independent set \(S \subseteq N_2(v)\), \(|N(S) \cap N(v)| \geq |S| + 2\), then \(G\) is pancyclic.