Forbidden Subgraphs for Hamiltonicity of 3-Connected Claw-Free Graphs
Jun Fujisawa · Journal of Graph Theory · 2012
In this article, we consider forbidden subgraphs for hamiltonicity of 3-connected claw-free graphs. Let be the graph obtained from a triangle by attaching a path of length i to one of its vertices, and let 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 -free graph G is hamiltonian unless G is the line graph of . It is shown in this article that this conjecture is true. Moreover, we investigate the set of connected graphs which satisfies that every 3-connected -free graph of sufficiently large order is hamiltonian if and only if A is a member of . We prove that, if , 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