Hamiltonicity of 3-connected line graphs

Weihua Yang*, Liming Xiong, Hongjian Lai, Xiaofeng Guo

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

Thomassen conjectured that every 4-connected line graph is Hamiltonian. Lai et al. conjectured [H. Lai, Y. Shao, H. Wu, J. Zhou, Every 3-connected, essentially 11-connected line graph is Hamiltonian, J. Combin. Theory Ser. B 96 (2006) 571-576] that every 3-connected, essentially 4-connected line graph is Hamiltonian. In this note, we first show that the conjecture posed by Lai et al. is not true and there is an infinite family of counterexamples; we show that 3-connected, essentially 4-connected line graph of a graph with at most 9 vertices of degree 3 is Hamiltonian; examples show that all conditions are sharp.

Original languageEnglish
Pages (from-to)1835-1838
Number of pages4
JournalApplied Mathematics Letters
Volume25
Issue number11
DOIs
Publication statusPublished - Nov 2012

Keywords

  • Collapsible graph Hamiltonian graph
  • Dominating
  • Eulerian subgraph
  • Line graph
  • Super-Eulerian graphs
  • Thomassen's conjecture

Fingerprint

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

Cite this