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. 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 ≠ v ∈ S such that d(u) + d(v) ≥ n or |N(u) ∩ N(v)| ≥ α (G); (ii) for any distinct u and v in S, |N(u) ∪ N(v)| ≥ n - max{d(x): x ∈ 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.
@article{bwmeta1.element.bwnjournal-article-doi-10_4064-cm120-1-5,
author = {Kewen Zhao and Ronald J. Gould},
title = {A note on the Song-Zhang theorem for Hamiltonian graphs},
journal = {Colloquium Mathematicae},
volume = {120},
year = {2010},
pages = {63-75},
zbl = {1225.05152},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-cm120-1-5}
}
Kewen Zhao; Ronald J. Gould. A note on the Song-Zhang theorem for Hamiltonian graphs. Colloquium Mathematicae, Tome 120 (2010) pp. 63-75. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-cm120-1-5/