Discrete Mathematics & Theoretical Computer Science (Jan 2005)

Every $3$-connected, essentially $11$-connected line graph is hamiltonian

  • Hong-Jian Lai,
  • Yehong Shao,
  • Ju Zhou,
  • Hehui Wu

DOI
https://doi.org/10.46298/dmtcs.3452
Journal volume & issue
Vol. DMTCS Proceedings vol. AE,..., no. Proceedings

Abstract

Read online

Thomassen conjectured that every $4$-connected line graph is hamiltonian. A vertex cut $X$ of $G$ is essential if $G-X$ has at least two nontrivial components. We prove that every $3$-connected, essentially $11$-connected line graph is hamiltonian. Using Ryjáček's line graph closure, it follows that every $3$-connected, essentially $11$-connected claw-free graph is hamiltonian.

Keywords