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

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

doi:10.46298/dmtcs.3452

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 hamiltonianConference paper

Authors: 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.

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: Line graph,claw-free graph,supereulerian graphs,collapsible graph,hamiltonian graph,dominating Eulerian subgraph,essential connectivity,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]

Bibliographic References

14 Documents citing this article

Xia Liu, 2022, A related problem on $s$ -Hamiltonian line graphs, AIMS Mathematics, 7, 10, pp. 19553-19561, 10.3934/math.20221073, https://doi.org/10.3934/math.20221073.

Xiaofeng Gu;Runrun Liu;Gexin Yu, 2022, Spanning tree packing and 2-essential edge-connectivity, Discrete Mathematics, 346, 1, pp. 113132, 10.1016/j.disc.2022.113132, https://doi.org/10.1016/j.disc.2022.113132.

Xiaofeng Gu;Wei Meng;Martin Rolek;Yue Wang;Gexin Yu, 2021, Sufficient Conditions for 2-Dimensional Global Rigidity, arXiv (Cornell University), 35, 4, pp. 2520-2534, 10.1137/20m1375498, https://arxiv.org/abs/2106.08539.

Tomáš Kaiser;Petr Vrána, 2020, The Hamiltonicity of essentially 9‐connected line graphs, arXiv (Cornell University), 97, 2, pp. 241-259, 10.1002/jgt.22653, https://arxiv.org/abs/2001.00042.

Weihua He;Weihua Yang, 2016, Hamiltonian paths in spanning subgraphs of line graphs, Discrete Mathematics, 340, 6, pp. 1359-1366, 10.1016/j.disc.2016.10.014.

Hao Li;Weihua He;Weihua Yang;Yandong Bai, 2015, Hamiltonian cycles in spanning subgraphs of line graphs, Discrete Applied Mathematics, 209, pp. 287-295, 10.1016/j.dam.2015.07.040.

Hao Li;Weihua He;Weihua Yang;Yandong Bai, 2015, A Note on Edge-Disjoint Hamilton Cycles in Line Graphs, Graphs and Combinatorics, 32, 2, pp. 741-744, 10.1007/s00373-015-1606-6.

Xiangwen Li;Yan Xiong, 2015, Collapsible graphs and Hamilton cycles of line graphs, Discrete Applied Mathematics, 194, pp. 132-142, 10.1016/j.dam.2015.05.030.

Hao Li;Weihua Yang, 2012, Every 3-connected essentially 10-connected line graph is Hamilton-connected, Discrete Mathematics, 312, 24, pp. 3670-3674, 10.1016/j.disc.2012.08.015, https://doi.org/10.1016/j.disc.2012.08.015.

Weihua Yang;Hongjian Lai;Hao Li;Xiaofeng Guo, 2012, Collapsible graphs and Hamiltonian connectedness of line graphs, Discrete Applied Mathematics, 160, 12, pp. 1837-1844, 10.1016/j.dam.2012.03.028, https://doi.org/10.1016/j.dam.2012.03.028.

Weihua Yang;Liming Xiong;Hongjian Lai;Xiaofeng Guo, 2012, Hamiltonicity of 3-connected line graphs, Applied Mathematics Letters, 25, 11, pp. 1835-1838, 10.1016/j.aml.2012.02.032.

H. J. Broersma;Z. Ryjáček;P. Vrána, 2011, How Many Conjectures Can You Stand? A Survey, Graphs and Combinatorics, 28, 1, pp. 57-75, 10.1007/s00373-011-1090-6, https://doi.org/10.1007/s00373-011-1090-6.

Tomáš Kaiser;Petr Vrána, 2011, Hamilton cycles in 5-connected line graphs, European Journal of Combinatorics, 33, 5, pp. 924-947, 10.1016/j.ejc.2011.09.015, https://doi.org/10.1016/j.ejc.2011.09.015.

János Barát;Matthias Kriesell, 2010, What is on his mind?, Discrete Mathematics, 310, 20, pp. 2573-2583, 10.1016/j.disc.2010.06.007, https://doi.org/10.1016/j.disc.2010.06.007.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 281 times.

This article's PDF has been downloaded 479 times.

Hong-Jian Lai ; Yehong Shao ; Ju Zhou ; Hehui Wu - Every 33-connected, essentially 1111-connected line graph is hamiltonian

Bibliographic References

14 Documents citing this article

Share and export

Consultation statistics

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