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 languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Publication statusPublished - 1998
Externally publishedYes

Keywords

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

Cite this