✦ LIBER ✦

Walks and paths in trees

✍ Scribed by Béla Bollobás; Mykhaylo Tyomkyn

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 159 KB
Volume: 70
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20600

No coin nor oath required. For personal study only.

✦ Synopsis

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 negative. Finally we consider an analogous question for paths rather than walks. © 2011 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

Toughness, trees, and walks

✍ Ellingham, M. N.; Zha, Xiaoya 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 1 views

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 grap

Cartesian products of trees and paths

✍ Bandelt, Hans-J�rgen; Burosch, Gustav; Laborde, Jean-Marie 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 581 KB

We characterize the (weak) Cartesian products of trees among median graphs by a forbidden 5-vertex convex subgraph. The number of tree factors (if finite) is half the length of a largest isometric cycle. Then a characterization of Cartesian products of n trees obtains in terms of isometric cycles an

Minimax trees, paths, and cut sets

✍ H. W. Corley; H. Golnabi 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB

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

Media montage: Knowing the path and walk

Media montage: Knowing the path and walking the path

✍ David Rosch; Trina Nocerino 📂 Article 📅 2007 🏛 John Wiley and Sons ⚖ 66 KB

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