• Title of article

    Hamiltonicity of 3-connected line graphs

  • Author/Authors

    Yang، نويسنده , , Weihua and Xiong، نويسنده , , Liming and Lai، نويسنده , , Hongjian and Guo، نويسنده , , Xiaofeng، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2012
  • Pages
    4
  • From page
    1835
  • To page
    1838
  • 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.
  • Keywords
    hamiltonian graph , Dominating Eulerian subgraph , Thomassen’s conjecture , Line graph , Super-Eulerian graphs , Collapsible graph
  • Journal title
    Applied Mathematics Letters
  • Serial Year
    2012
  • Journal title
    Applied Mathematics Letters
  • Record number

    1528553