✦ LIBER ✦

Toughness, trees, and walks

✍ Scribed by Ellingham, M. N.; Zha, Xiaoya

Publisher: John Wiley and Sons
Year: 2000
Tongue: English
Weight: 167 KB
Volume: 33
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(200003)33:3<125::aid-jgt1>3.0.co;2-x

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Walks and paths in trees

✍ Béla Bollobás; Mykhaylo Tyomkyn 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB

## Abstract Recently Csikvári [Combinatorica 30(2) 2010, 125–137] proved a conjecture of Nikiforov concerning the number of closed walks on trees. Our aim is to extend this theorem to all walks. In addition, we give a simpler proof of Csikvári's result and answer one of his questions in the negativ

Walking the Tree

✍ Warren, Kaaron 📂 Fiction 📅 2011 🏛 Angry Robot 🌐 English ⚖ 216 KB 👁 3 views

**Botanica is an island, but almost all of the island is taken up by the Tree.** Little knowing how they came to be here, small communities live around the coast line. The Tree provides them shelter, kindling, medicine – and a place of legends, for there are ghosts within the trees who snatch child

Like Trees, Walking

✍ Ravi Howard 📂 Fiction 🏛 HarperCollins 🌐 English ⚖ 139 KB 👁 3 views

Based on the true story of a modern-day lynching in America, Ravi Howard's widely acclaimed debut novel exposes one of the most tragic chapters in the history of the American South. On the morning of March 21, 1981, in Mobile, Alabama, nineteen-year-old Michael Donald was found dead, his body badl

On spanning trees and walks of low maxim

On spanning trees and walks of low maximum degree

✍ Daniel P. Sanders; Yue Zhao 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 86 KB 👁 3 views

Extremal cover times for random walks on

Extremal cover times for random walks on trees

✍ Graham Brightwell; Peter Winkler 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 370 KB

## Abstract Let __C~ν~__(__T__) denote the “cover time” of the tree __T__ from the vertex __v__, that is, the expected number of steps before a random walk starting at __v__ hits every vertex of __T.__ Asymptotic lower bounds for __C~ν~__(__T__) (for __T__ a tree on __n__ vertices) have been obtain

Death Walks the Woods (That Yew Tree's S

Death Walks the Woods (That Yew Tree's Shade)

✍ Cyril Hare 📂 Fiction 📅 1954 🏛 Reading Essentials 🌐 English ⚖ 110 KB 👁 1 views

The picturesque village of Yew Hill, Markshire becomes an idyllic retreat for Francis Pettigrew and his wife until Francis is suddenly summoned to sit in as the County Court Judge and an elderly neighbor is brutally murdered.