TY - JOUR
T1 - Closures and heavy pairs for hamiltonicity
AU - Shang, Wangyi
AU - Broersma, Hajo
AU - Zhang, Shenggui
AU - Li, Binlong
N1 - Publisher Copyright:
© 2025 Elsevier B.V.
PY - 2025/11/15
Y1 - 2025/11/15
N2 - We say that a graph G on n vertices is {H,F}-o-heavy if every induced subgraph of G isomorphic to H or F contains two nonadjacent vertices with degree sum at least n. Generalizing earlier sufficient forbidden subgraph conditions for hamiltonicity, in 2012, Li, Ryjáček, Wang and Zhang determined all connected graphs R and S of order at least 3 other than P3 such that every 2-connected {R,S}-o-heavy graph is hamiltonian. In particular, they showed that, up to symmetry, R must be a claw and S∈{P4,P5,C3,Z1,Z2,B,N,W}. In 2008, Čada extended Ryjáček's closure concept for claw-free graphs by introducing what we call the c-closure for claw-o-heavy graphs. We apply it here to characterize the structure of the c-closure of 2-connected {R,S}-o-heavy graphs, where R and S are as above. Our main results extend or generalize several earlier results on hamiltonicity involving forbidden or o-heavy subgraphs.
AB - We say that a graph G on n vertices is {H,F}-o-heavy if every induced subgraph of G isomorphic to H or F contains two nonadjacent vertices with degree sum at least n. Generalizing earlier sufficient forbidden subgraph conditions for hamiltonicity, in 2012, Li, Ryjáček, Wang and Zhang determined all connected graphs R and S of order at least 3 other than P3 such that every 2-connected {R,S}-o-heavy graph is hamiltonian. In particular, they showed that, up to symmetry, R must be a claw and S∈{P4,P5,C3,Z1,Z2,B,N,W}. In 2008, Čada extended Ryjáček's closure concept for claw-free graphs by introducing what we call the c-closure for claw-o-heavy graphs. We apply it here to characterize the structure of the c-closure of 2-connected {R,S}-o-heavy graphs, where R and S are as above. Our main results extend or generalize several earlier results on hamiltonicity involving forbidden or o-heavy subgraphs.
KW - Claw-free graph
KW - Claw-o-heavy graph
KW - Closure
KW - Hamiltonian graph
KW - Heavy subgraph
UR - http://www.scopus.com/inward/record.url?scp=105007318438&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2025.05.028
DO - 10.1016/j.dam.2025.05.028
M3 - 文章
AN - SCOPUS:105007318438
SN - 0166-218X
VL - 375
SP - 25
EP - 37
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -