Clique covering and degree conditions for hamiltonicity in claw-free graphs

By using the closure concept introduced by the last author, we prove that for any sufficiently large nonhamiltonian claw-free graph G satisfying a degree condition of type sigma (k)(G) > n + k(2) - 4k + 7 (where k is a constant), the closure of G can be covered by at most k - 1 cliques. Using structural properties of the closure concept, we show a method for characterizing all such nonhamiltonian exceptional graphs with limited clique covering number. The method is explicitly carried out for k less than or equal to 6 and illustrated by proving that every 2-connected claw-free graph G of order n greater than or equal to 77 with delta (G) greater than or equal to 14 and sigma (6)(G) > n + 19 is either hamiltonian or belongs to a family of easily described exceptions. (C) 2001 Elsevier Science B.V. All rights reserved.