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

  • 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.

https://doi.org/10.46298/dmtcs.3452
Source: HAL:hal-01184441v1
Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: essential connectivity,Line graph,claw-free graph,supereulerian graphs,collapsible graph,hamiltonian graph,dominating Eulerian subgraph,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1112/jlms/s1-36.1.221
  • 10.1112/jlms/s1-36.1.221
On the Problem of Decomposing a Graph into n Connected Factors

Share and export

Consultation statistics

This page has been seen 151 times.
This article's PDF has been downloaded 374 times.