A note on the Song–Zhang theorem for Hamiltonian graphs
Volume 120 / 2010
Colloquium Mathematicum 120 (2010), 63-75
MSC: 05C38, 05C45.
DOI: 10.4064/cm120-1-5
Abstract
An independent set of a graph G is said to be essential if S has a pair of vertices that are distance two apart in G. In 1994, Song and Zhang proved that if for each independent set S of cardinality k+1, one of the following condition holds:
(i) there exist u \neq v \in S such that d(u) + d(v) \geq n or |N(u) \cap N(v)| \geq \alpha (G);
(ii) for any distinct u and v in S, |N(u) \cup N(v)| \geq n - \max \{d(x): x \in S\},
then G is Hamiltonian. We prove that if for each essential independent set S of cardinality k+1, one of conditions (i) or (ii) holds, then G is Hamiltonian. A number of known results on Hamiltonian graphs are corollaries of this result.
