Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 25-37 |
| Number of pages | 13 |
| Journal | Discrete applied mathematics |
| Volume | 375 |
| DOIs | |
| Publication status | Published - 15 Nov 2025 |
Keywords
- 2025 OA procedure
- Claw-o-heavy graph
- Closure
- Hamiltonian graph
- Heavy subgraph
Fingerprint
Dive into the research topics of 'Closures and heavy pairs for hamiltonicity'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver