Hamiltonian Cycles in Regular 2-Connected Claw-Free Graphs

摘要

A known result by Jackson Bill is that every 2-connected κ-regular graph on at most 3κ vertices is Hamiltonian. In this paper, it is proved that every 2-connected κ-regular claw-free graph on at most 5κ(κ≥10) vertices is Hamiltonian. Moreover, the bound 5κ is best possible. A counterexample of a 2-connected κ-regular claw-free non-Hamiltonian graph on 5κ+ 1 vertices is given, and it is conjectured that every 3-connected κ-reg-ular claw-free graph on at most 12κ -7 vertices is Hamiltonian.