Informace o publikaci
Tough spiders
| Autoři | |
|---|---|
| Rok publikování | 2007 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Journal of Graph Theory |
| Citace | |
| Doi | http://dx.doi.org/10.1002/jgt.20244 |
| Klíčová slova | hamilton cycles; toughness; interval graphs; split graphs; matroids |
| Popis | 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. |