On 3-connected hamiltonian line graphs

Ye Chen, Suohai Fan, Hong Jian Lai

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Thomassen conjectured that every 4-connected line graph is hamiltonian. It has been proved that every 4-connected line graph of a claw-free graph, or an almost claw-free graph, or a quasi-claw-free graph, is hamiltonian. In 1998, Ainouche et al. [2] introduced the class of DCT graphs, which properly contains both the almost claw-free graphs and the quasi-claw-free graphs. Recently, Broersma and Vumar (2009) [5] found another family of graphs, called P3D graphs, which properly contain all quasi-claw-free graphs. In this paper, we investigate the hamiltonicity of 3-connected line graphs of DCT graphs and P3D graphs, and prove that if G is a DCT graph or a P3D graph with κ(L(G))<3 and if L(G) does not have an independent vertex 3-cut, then L(G) is hamiltonian. Consequently, every 4-connected line graph of a DCT graph or a P3D graph is hamiltonian.

Original languageEnglish (US)
Pages (from-to)1877-1882
Number of pages6
JournalDiscrete Mathematics
Issue number11
StatePublished - Jun 6 2012
Externally publishedYes


  • Claw-free graph
  • Collapsible graph
  • DCT graph
  • Hamiltonian graph
  • Line graph
  • P3D graph
  • Supereulerian graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'On 3-connected hamiltonian line graphs'. Together they form a unique fingerprint.

Cite this