On s-Hamiltonian-Connected Line Graphs

Xiaoling Ma, Hong Jian Lai, Mingquan Zhan, Taoye Zhang, Ju Zhou

Research output: Contribution to journalArticlepeer-review


For an integer s ≥ 0, G is s-hamiltonian-connected if for any vertex subset S ⊆ V (G) with |S| ≤ s, G - S is hamiltonian-connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see [Reflections on graph theory, J. Graph Theory 10 (1986) 309-324]), and Kuž el and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian-connected (see [Z. Ryjáček and P. Vrána, Line graphs of multigraphs and Hamilton-connectedness of claw-free graphs, J. Graph Theory 66 (2011) 152-173]). In this paper we prove the following. (i) For s ≥ 3, every (s + 4)-connected line graph is s-hamiltonian-connected. (ii) For s ≥ 0, every (s + 4)-connected line graph of a claw-free graph is s-hamiltonian-connected.

Original languageEnglish (US)
JournalDiscussiones Mathematicae - Graph Theory
StateAccepted/In press - 2022

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'On s-Hamiltonian-Connected Line Graphs'. Together they form a unique fingerprint.

Cite this