A note on the Song-Zhang theorem for Hamiltonian graphs

• Autorzy: Kewen Zhao , Ronald J. Gould
• Języki publikacji: EN

Abstrakty

EN

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.

Kategorie tematyczne

• 05C45: Eulerian and Hamiltonian graphs
• 05C38: Paths and cycles

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Colloquium Mathematicum
• Rocznik: 2010
• Tom: 120
• Numer: 1
• Strony: 63-75

Daty

wydano

2010

Twórcy

autor

Kewen Zhao

• Department of Mathematics, Qiongzhou University, Sanya, Hainan 572022, P.R. China

autor

Ronald J. Gould

• Deptartment of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, U.S.A.

Identyfikatory

DOI

10.4064/cm120-1-5