TY - JOUR
T1 - Degree and neighborhood intersection conditions restricted to induced subgraphs ensuring Hamiltonicity of graphs
AU - Ning, Bo
AU - Zhang, Shenggui
AU - Chen, Bing
N1 - Publisher Copyright:
© 2014 World Scientific Publishing Company.
PY - 2014/9/1
Y1 - 2014/9/1
N2 - Let claw be the graph K1,3. A graph G on n ≥ 3 vertices is called o-heavy if each induced claw of G has a pair of end-vertices with degree sum at least n, and called 1-heavy if at least one end-vertex of each induced claw of G has degree at least n/2. In this note, we show that every 2-connected o-heavy or 3-connected 1-heavy graph is Hamiltonian if we restrict Fan-type degree condition or neighborhood intersection condition to certain pairs of vertices in some small induced subgraphs of the graph. Our results improve or extend previous results of Broersma et al., Chen et al., Fan, Goodman and Hedetniemi, Gould and Jacobson, and Shi on the existence of Hamilton cycles in graphs.
AB - Let claw be the graph K1,3. A graph G on n ≥ 3 vertices is called o-heavy if each induced claw of G has a pair of end-vertices with degree sum at least n, and called 1-heavy if at least one end-vertex of each induced claw of G has degree at least n/2. In this note, we show that every 2-connected o-heavy or 3-connected 1-heavy graph is Hamiltonian if we restrict Fan-type degree condition or neighborhood intersection condition to certain pairs of vertices in some small induced subgraphs of the graph. Our results improve or extend previous results of Broersma et al., Chen et al., Fan, Goodman and Hedetniemi, Gould and Jacobson, and Shi on the existence of Hamilton cycles in graphs.
KW - claw-free (1-heavy, 2-heavy, o-heavy) graph
KW - Hamilton cycle
KW - induced subgraph
UR - http://www.scopus.com/inward/record.url?scp=85042809468&partnerID=8YFLogxK
U2 - 10.1142/S1793830914500438
DO - 10.1142/S1793830914500438
M3 - 文章
AN - SCOPUS:85042809468
SN - 1793-8309
VL - 6
JO - Discrete Mathematics, Algorithms and Applications
JF - Discrete Mathematics, Algorithms and Applications
IS - 3
M1 - 1450043
ER -