A note on the Song–Zhang theorem for Hamiltonian graphs

Kewen Zhao¹ ; Ronald J. Gould²

¹ Department of Mathematics Qiongzhou University Sanya, Hainan 572022 P.R. China
² Deptartment of Mathematics and Computer Science Emory University Atlanta, GA 30322, U.S.A.

Colloquium Mathematicum, Tome 120 (2010) no. 1, pp. 63-75

Résumé

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 \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.

Détail

DOI : 10.4064/cm120-1-5

Keywords: independent set graph said essential has pair vertices distance apart song zhang proved each independent set cardinality following condition holds there exist neq geq cap geq alpha distinct cup geq max hamiltonian prove each essential independent set cardinality conditions holds hamiltonian number known results hamiltonian graphs corollaries result