Premium
Hourglasses and Hamilton cycles in 4‐connected claw‐free graphs
Author(s) -
Kaiser Tomáš,
Li MingChu,
Ryjáček Zdeněk,
Xiong Liming
Publication year - 2005
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.20056
Subject(s) - combinatorics , mathematics , claw , hourglass , induced subgraph , conjecture , distance hereditary graph , hamiltonian path , hamiltonian (control theory) , chordal graph , graph , discrete mathematics , graph power , line graph , physics , mechanical engineering , mathematical optimization , astronomy , vertex (graph theory) , engineering
Abstract We show that if G is a 4‐connected claw‐free graph in which every induced hourglass subgraph S contains two non‐adjacent vertices with a common neighbor outside S , then G is hamiltonian. This extends the fact that 4‐connected claw‐free, hourglass‐free graphs are hamiltonian, thus proving a broader special case of a conjecture by Matthews and Sumner. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 267–276, 2005