It is shown that claw-free Hamiltonian simple graphs with minimum degree at least $c$ times the order can be recognized in polynomial time, for any positive constant $c$. The method used is exemplified by proving that every 2-connected claw-free simple graph $G$ of sufficiently large order $n$ with minimum degree $\delta(G) \geq (n+19)/6$ is Hamiltonian or belongs to one of ten classes of exceptional graphs, which can be recognized in polynomial time. Similarly it is shown that every 3-connected claw-free simple graph $G$ of sufficiently large order $n$ with $\delta(G) \geq (n+29)/8$ is Hamiltonian. These results strengthen previously known results.
|Place of Publication||Enschede|
|Publisher||University of Twente, Department of Applied Mathematics|
|Publication status||Published - 1998|