Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184441
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 2:59:03 PM
Last modification on : Sunday, September 20, 2020 - 5:12:02 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:12:53 AM

File

dmAE0173.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184441, version 1

Collections

Citation

Hong-Jian Lai, Yehong Shao, Ju Zhou, Hehui Wu. Every $3$-connected, essentially $11$-connected line graph is hamiltonian. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.379-382. ⟨hal-01184441⟩

Share

Metrics

Record views

379

Files downloads

1156