# Recognizing claw-free Hamiltonian graphs with large minimum degree

E.J. Kuipers, H.J. Veldman

Research output: Book/ReportReportOther research output

## Abstract

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.
Original language Undefined Enschede University of Twente, Department of Applied Mathematics Published - 1998 Yes

• MSC-05C35
• MSC-05C45
• EWI-3257