Premium
Toughness, trees, and walks
Author(s) -
Ellingham M. N.,
Zha Xiaoya
Publication year - 2000
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/(sici)1097-0118(200003)33:3<125::aid-jgt1>3.0.co;2-x
Subject(s) - combinatorics , mathematics , random walk , conjecture , vertex (graph theory) , spanning tree , graph , regular graph , discrete mathematics , graph power , line graph , statistics
A graph is t‐tough if the number of components of G \ S is at most | S |/ t for every cutset S ⊆ V ( G ). A k‐walk in a graph is a spanning closed walk using each vertex at most k times. When k = 1, a 1‐walk is a Hamilton cycle, and a longstanding conjecture by Chvátal is that every sufficiently tough graph has a 1‐walk. When k ≥ 3, Jackson and Wormald used a result of Win to show that every sufficiently tough graph has a k ‐walk. We fill in the gap between k = 1 and k ≥ 3 by showing that, when k = 2, every sufficiently tough (specifically, 4‐tough) graph has a 2‐walk. To do this we first provide a new proof for and generalize a result by Win on the existence of a k‐tree , a spanning tree with every vertex of degree at most k . We also provide new examples of tough graphs with no k ‐walk for k ≥ 2. © 2000 John Wiley & Sons, Inc. J Graph Theory 33:125–137, 2000