Premium
Forbidden Subgraphs for Hamiltonicity of 3‐Connected Claw‐Free Graphs
Author(s) -
Fujisawa Jun
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21663
Subject(s) - combinatorics , mathematics , line graph , discrete mathematics , path graph , distance hereditary graph , symmetric graph , complement graph , bound graph , factor critical graph , graph power , graph , voltage graph
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