Premium
Every 3‐connected claw‐free Z 8 ‐free graph is Hamiltonian
Author(s) -
Lai HongJian,
Xiong Liming,
Yan Huiya,
Yan Jin
Publication year - 2010
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.20433
Subject(s) - combinatorics , mathematics , distance hereditary graph , factor critical graph , induced subgraph , vertex (graph theory) , quartic graph , graph , discrete mathematics , path graph , regular graph , complement graph , line graph , graph power
In this article, we first show that every 3‐edge‐connected graph with circumference at most 8 is supereulerian, which is then applied to show that a 3‐connected claw‐free graph without Z 8 as an induced subgraph is Hamiltonian, where Z 8 denotes the graph derived from identifying one end vertex of P 9 (a path with 9 vertices) with one vertex of a triangle. The above two results are both best possible in a sense that the number 8 cannot be replaced by 9 and they also extend former results by Brousek et al . in (Discrete Math 196 (1999), 29–50) and by Łuczak and Pfender in (J Graph Theory 47 (2004), 111–121). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 1–11, 2010