Article ID Journal Published Year Pages File Type
4647935 Discrete Mathematics 2012 13 Pages PDF
Abstract

We strengthen the closure concept for Hamilton-connectedness in claw-free graphs, introduced by the second and fourth authors, such that the strong closure GMGM of a claw-free graph GG is the line graph of a multigraph containing at most two triangles or at most one double edge.Using the concept of strong closure, we prove that a 3-connected claw-free graph GG is Hamilton-connected if GG satisfies one of the following: (i) GG can be covered by at most 5 cliques, (ii) δ(G)≥4δ(G)≥4 and GG can be covered by at most 6 cliques, (iii) δ(G)≥6δ(G)≥6 and GG can be covered by at most 7 cliques.Finally, by reconsidering the relation between degree conditions and clique coverings in the case of the strong closure GMGM, we prove that every 3-connected claw-free graph GG of minimum degree δ(G)≥24δ(G)≥24 and minimum degree sum σ8(G)≥n+50σ8(G)≥n+50 (or, as a corollary, of order n≥142n≥142 and minimum degree δ(G)≥n+508) is Hamilton-connected.We also show that our results are asymptotically sharp.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,