Forbidden Subgraphs for Hamiltonicity of 3‐Connected Claw‐Free Graphs

In this article, we consider forbidden subgraphs for hamiltonicity of 3‐connected claw‐free graphs. Let Z i be the graph obtained from a triangle by attaching a path of length i to one of its vertices, and let Q * be the graph obtained from the Petersen graph by adding one pendant edge to each vertex. Lai et al. (J Graph Theory 64(1) (2010), 1–11) conjectured that every 3‐connected { K 1 , 3 , Z 9 } ‐free graph G is hamiltonian unless G is the line graph of Q * . It is shown in this article that this conjecture is true. Moreover, we investigate the set of connected graphs A 3 which satisfies that every 3‐connected { K 1 , 3 , A } ‐free graph of sufficiently large order is hamiltonian if and only if A is a member of A 3 . We prove that, if G ∈ A 3 , then G is a graph on at most 12 vertices with the following structure: (i) a path of length at most 10, (ii) a triangle with three vertex‐disjoint paths of total length at most 9, or (iii) G consists of two triangles connected by a path of length 1, 3, 5, or 7. AMS classification: 05C45, 05C38, 05C75 . © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 146–160, 2013