Skip to main content
Second Hamiltonian cycles in claw-free graphs
Theory and Applications of Graphs
  • Hossein Esfandiari
  • Colton Magnant, Georgia Southern University
  • Pouria Salehi Nowbandegani
  • Shirdareh Haghighi
Publication Date
Sheehan conjectured in 1975 that every Hamiltonian regular simple graph of even degree at least four contains a second Hamiltonian cycle. We prove that most claw-free Hamiltonian graphs with minimum degree at least 3 have a second Hamiltonian cycle and describe the structure of those graphs not covered by our result. By this result, we show that Sheehan’s conjecture holds for claw-free graphs whose order is not divisible by 6. In addition, we believe that the structure that we introduce can be useful for further studies on claw-free graphs.
Citation Information
Hossein Esfandiari, Colton Magnant, Pouria Salehi Nowbandegani and Shirdareh Haghighi. "Second Hamiltonian cycles in claw-free graphs" (2015)
Available at: