Premium
Claw‐free 3‐connected P 11 ‐free graphs are hamiltonian
Author(s) -
Łuczak Tomasz,
Pfender Florian
Publication year - 2004
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.20019
Subject(s) - mathematics , combinatorics , claw , hamiltonian (control theory) , hamiltonian path , pancyclic graph , graph , discrete mathematics , line graph , pathwidth , mechanical engineering , engineering , mathematical optimization
We show that every 3‐connected claw‐free graph which contains no induced copy of P 11 is hamiltonian. Since there exist non‐hamiltonian 3‐connected claw‐free graphs without induced copies of P 12 this result is, in a way, best possible. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 111–121, 2004