## Abstract

In this article, we consider forbidden subgraphs for hamiltonicity of 3-connected claw-free graphs. Let Zi 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 {K1,3,Z9}-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 A3 which satisfies that every 3-connected {K1,3,A}-free graph of sufficiently large order is hamiltonian if and only if A is a member of A3. We prove that, if Gâ̂̂A3, 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.

Original language | English |
---|---|

Pages (from-to) | 146-160 |

Number of pages | 15 |

Journal | Journal of Graph Theory |

Volume | 73 |

Issue number | 2 |

DOIs | |

Publication status | Published - 2013 Jun |

## Keywords

- Hamiltonian cycle
- Ryjáč eks closure
- claw-free graphs
- forbidden subgraphs

## ASJC Scopus subject areas

- Geometry and Topology