TY - JOUR
T1 - Hamilton cycles in claw-heavy graphs
AU - Chen, Bing
AU - Zhang, Shenggui
AU - Qiao, Shengning
PY - 2009/4/28
Y1 - 2009/4/28
N2 - A graph G on n ≥ 3 vertices is called claw-heavy if every induced claw (K1, 3) of G has a pair of nonadjacent vertices such that their degree sum is at least n. In this paper we show that a claw-heavy graph G has a Hamilton cycle if we impose certain additional conditions on G involving numbers of common neighbors of some specific pair of nonadjacent vertices, or forbidden induced subgraphs. Our results extend two previous theorems of Broersma, Ryjáček and Schiermeyer [H.J. Broersma, Z. Ryjáček, I. Schiermeyer, Dirac's minimum degree condition restricted to claws, Discrete Math. 167-168 (1997) 155-166], on the existence of Hamilton cycles in 2-heavy graphs.
AB - A graph G on n ≥ 3 vertices is called claw-heavy if every induced claw (K1, 3) of G has a pair of nonadjacent vertices such that their degree sum is at least n. In this paper we show that a claw-heavy graph G has a Hamilton cycle if we impose certain additional conditions on G involving numbers of common neighbors of some specific pair of nonadjacent vertices, or forbidden induced subgraphs. Our results extend two previous theorems of Broersma, Ryjáček and Schiermeyer [H.J. Broersma, Z. Ryjáček, I. Schiermeyer, Dirac's minimum degree condition restricted to claws, Discrete Math. 167-168 (1997) 155-166], on the existence of Hamilton cycles in 2-heavy graphs.
KW - 2-heavy graph
KW - Claw-heavy graph
KW - Hamilton cycle
UR - http://www.scopus.com/inward/record.url?scp=62849100983&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2008.04.013
DO - 10.1016/j.disc.2008.04.013
M3 - 文章
AN - SCOPUS:62849100983
SN - 0012-365X
VL - 309
SP - 2015
EP - 2019
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 8
ER -