Closures and heavy pairs for hamiltonicity

Wangyi Shang, Hajo Broersma, Shenggui Zhang, Binlong Li

科研成果: 期刊稿件文章同行评审

摘要

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.

源语言英语
页(从-至)25-37
页数13
期刊Discrete Applied Mathematics
375
DOI
出版状态已出版 - 15 11月 2025

引用此