DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

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

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

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.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional