Closures and heavy pairs for hamiltonicity

Wangyi Shang, Hajo Broersma, Shenggui Zhang, Binlong Li

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)25-37
Number of pages13
JournalDiscrete Applied Mathematics
Volume375
DOIs
StatePublished - 15 Nov 2025

Keywords

  • Claw-free graph
  • Claw-o-heavy graph
  • Closure
  • Hamiltonian graph
  • Heavy subgraph

Cite this