Premium
Tough spiders
Author(s) -
Kaiser Tomáš,
Král Daniel,
Stacho Ladislav
Publication year - 2007
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.20244
Subject(s) - chordal graph , combinatorics , mathematics , indifference graph , hamiltonian path , split graph , pathwidth , graph , spider , interval graph , outerplanar graph , discrete mathematics , 1 planar graph , line graph , physics , astronomy
Spider graphs are the intersection graphs of subtrees of subdivisions of stars. Thus, spider graphs are chordal graphs that form a common superclass of interval and split graphs. Motivated by previous results on the existence of Hamilton cycles in interval, split and chordal graphs, we show that every 3/2‐tough spider graph is hamiltonian. The obtained bound is best possible since there are (3/2 – ε)‐tough spider graphs that do not contain a Hamilton cycle. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 23–40, 2007