Publication details
Tough spiders
| Authors | |
|---|---|
| Year of publication | 2007 |
| Type | Article in Periodical |
| Magazine / Source | Journal of Graph Theory |
| Citation | |
| Doi | http://dx.doi.org/10.1002/jgt.20244 |
| Keywords | hamilton cycles; toughness; interval graphs; split graphs; matroids |
| Description | 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 - epsilon)-tough spider graphs that do not contain a Hamilton cycle. (C) 2007 Wiley Periodicals. |