Hong-Jian Lai ; Yehong Shao ; Ju Zhou ; Hehui Wu
-
Every $3$-connected, essentially $11$-connected line graph is hamiltonian
dmtcs:3452 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
-
https://doi.org/10.46298/dmtcs.3452
Every $3$-connected, essentially $11$-connected line graph is hamiltonian
Authors: Hong-Jian Lai 1; Yehong Shao 1; Ju Zhou 1; Hehui Wu 1
NULL##NULL##NULL##NULL
Hong-Jian Lai;Yehong Shao;Ju Zhou;Hehui Wu
1 Department of Mathematics [Morgantown]
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.