Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Every $3$-connected, ...
Conference paper

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

Hong-Jian Lai (1), Yehong Shao (1), Ju Zhou (1), Hehui Wu (1)
(1) Department of Mathematics [Morgantown]
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2004
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Proceedings
DOI
10.46298/dmtcs.3452
License
https://about.hal.science/hal-authorisation-v1
Indicators
598
Views
816
Downloads

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

Hong-Jian Lai (1), Yehong Shao (1), Ju Zhou (1), Hehui Wu (1)
(1) Department of Mathematics [Morgantown]
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • Line graph
  • claw-free graph
  • supereulerian graphs
  • collapsible graph
  • hamiltonian graph
  • dominating Eulerian subgraph
  • essential connectivity
Cited by

Source: OpenCitations

  • What is on his mind?

    Discrete Mathematics

    Authors : János Barát ORCID, Matthias Kriesell ORCID

    Journal reference : Volume 310, 2010, pp. 2573-2583

    DOI : 10.1016/j.disc.2010.06.007

  • Spanning tree packing and 2-essential edge-connectivity

    Discrete Mathematics

    Authors : Xiaofeng Gu ORCID, Runrun Liu ORCID, Gexin Yu ORCID

    Journal reference : Volume 346, 2022, pp. 113132

    DOI : 10.1016/j.disc.2022.113132

  • Collapsible graphs and Hamilton cycles of line graphs

    Discrete Applied Mathematics

    Authors : Xiangwen Li ORCID, Yan Xiong ORCID

    Journal reference : Volume 194, 2015, pp. 132-142

    DOI : 10.1016/j.dam.2015.05.030

  • Note on the rigidity of graphs

    Filomat

    Authors : Long Jin, Jianxi Li ORCID, Peng Huang ORCID

    Journal reference : Volume 39, 2025, pp. 6423-6436

    DOI : 10.2298/fil2518423j

  • How Many Conjectures Can You Stand? A Survey

    Graphs and Combinatorics

    Authors : H. J. Broersma ORCID, Z. Ryjáček ORCID, P. Vrána ORCID

    Journal reference : Volume 28, 2011, pp. 57-75

    DOI : 10.1007/s00373-011-1090-6

  • A Note on Edge-Disjoint Hamilton Cycles in Line Graphs

    Graphs and Combinatorics

    Authors : Hao Li ORCID, Weihua He ORCID, Weihua Yang, Yandong Bai ORCID

    Journal reference : Volume 32, 2015, pp. 741-744

    DOI : 10.1007/s00373-015-1606-6

  • Hamiltonian cycles in spanning subgraphs of line graphs

    Discrete Applied Mathematics

    Authors : Hao Li ORCID, Weihua He ORCID, Weihua Yang, Yandong Bai ORCID

    Journal reference : Volume 209, 2015, pp. 287-295

    DOI : 10.1016/j.dam.2015.07.040

  • Hamiltonian paths in spanning subgraphs of line graphs

    Discrete Mathematics

    Authors : Weihua He ORCID, Weihua Yang

    Journal reference : Volume 340, 2016, pp. 1359-1366

    DOI : 10.1016/j.disc.2016.10.014

  • Sufficient Conditions for 2-Dimensional Global Rigidity

    SIAM Journal on Discrete Mathematics

    Authors : Xiaofeng Gu ORCID, Wei Meng ORCID, Martin Rolek ORCID, Yue Wang ORCID, Gexin Yu ORCID

    Journal reference : Volume 35, 2021, pp. 2520-2534

    DOI : 10.1137/20m1375498

  • Hamiltonicity of 3-connected line graphs

    Applied Mathematics Letters

    Authors : Weihua Yang, Liming Xiong ORCID, Hongjian Lai ORCID, Xiaofeng Guo

    Journal reference : Volume 25, 2012, pp. 1835-1838

    DOI : 10.1016/j.aml.2012.02.032

  • The Hamiltonicity of essentially 9‐connected line graphs

    arXiv (Cornell University)

    Authors : Tomáš Kaiser ORCID, Petr Vrána ORCID

    Journal reference : Volume 97, 2020, pp. 241-259

    DOI : 10.1002/jgt.22653

  • A related problem on $ s $-Hamiltonian line graphs

    AIMS Mathematics

    Authors : Xia Liu ORCID

    Journal reference : Volume 7, 2022, pp. 19553-19561

    DOI : 10.3934/math.20221073

  • Collapsible graphs and Hamiltonian connectedness of line graphs

    Discrete Applied Mathematics

    Authors : Weihua Yang, Hongjian Lai ORCID, Hao Li ORCID, Xiaofeng Guo

    Journal reference : Volume 160, 2012, pp. 1837-1844

    DOI : 10.1016/j.dam.2012.03.028

  • Every 3-connected essentially 10-connected line graph is Hamilton-connected

    Discrete Mathematics

    Authors : Hao Li ORCID, Weihua Yang

    Journal reference : Volume 312, 2012, pp. 3670-3674

    DOI : 10.1016/j.disc.2012.08.015

  • Hamilton cycles in 5-connected line graphs

    European Journal of Combinatorics

    Authors : Tomáš Kaiser ORCID, Petr Vrána ORCID

    Journal reference : Volume 33, 2011, pp. 924-947

    DOI : 10.1016/j.ejc.2011.09.015
Preview
Loading PDF preview...