A note on the Song-Zhang theorem for Hamiltonian graphs

Kewen Zhao, and Ronald J. Gould. "A note on the Song-Zhang theorem for Hamiltonian graphs." Colloquium Mathematicae 120.1 (2010): 63-75. <http://eudml.org/doc/284050>.

@article{KewenZhao2010,
abstract = { 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. },
author = {Kewen Zhao, Ronald J. Gould},
journal = {Colloquium Mathematicae},
language = {eng},
number = {1},
pages = {63-75},
title = {A note on the Song-Zhang theorem for Hamiltonian graphs},
url = {http://eudml.org/doc/284050},
volume = {120},
year = {2010},
}

TY - JOUR
AU - Kewen Zhao
AU - Ronald J. Gould
TI - A note on the Song-Zhang theorem for Hamiltonian graphs
JO - Colloquium Mathematicae
PY - 2010
VL - 120
IS - 1
SP - 63
EP - 75
AB - 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.
LA - eng
UR - http://eudml.org/doc/284050
ER -