𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Diameter of random spanning trees in a given graph

✍ Scribed by Fan Chung; Paul Horn; L. Lu

Publisher
John Wiley and Sons
Year
2011
Tongue
English
Weight
144 KB
Volume
69
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Motivated by the observation that the sparse tree‐like subgraphs in a small world graph have large diameter, we analyze random spanning trees in a given host graph. We show that the diameter of a random spanning tree of a given host graph G is between and with high probability., where c and cβ€² depend on the spectral gap of G and the ratio of the moments of the degree sequence. For the special case of regular graphs, this result improves the previous lower bound by Aldous by a factor of log__n__. Copyright Β© 2011 John Wiley Periodicals, Inc. J Graph Theory 69:
223–240, 2012

πŸ“œ SIMILAR VOLUMES

A note on graphs with diameter-preservin
A note on graphs with diameter-preserving spanning trees
✍ Fred Buckley; Martin Lewinter πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 182 KB πŸ‘ 1 views

The distance between a pair of vertices u, u in a graph G is the length of a shortest path joining u and u. The diameter diam(G) of G is the maximum distance between all pairs of vertices in G. A spanning tree Tof G is diameter preserving if diam(T) = diam(G). In this note, we characterize graphs th

Vertices of given degree in a random gra
Vertices of given degree in a random graph
✍ BΓ©la BollobΓ‘s πŸ“‚ Article πŸ“… 1982 πŸ› John Wiley and Sons 🌐 English βš– 349 KB πŸ‘ 1 views
The distribution of nodes of given degre
The distribution of nodes of given degree in random trees
✍ Drmota, Michael; Gittenberger, Bernhard πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 391 KB πŸ‘ 2 views

Let T n denote the set of unrooted unlabeled trees of size n and let k β‰₯ 1 be given. By assuming that every tree of T n is equally likely, it is shown that the limiting distribution of the number of nodes of degree k is normal with mean value ∼ Β΅ k n and variance ∼ Οƒ 2 k n with positive constants Β΅

On the number of vertices of given degre
On the number of vertices of given degree in a random graph
✍ Zbigniew Palka πŸ“‚ Article πŸ“… 1984 πŸ› John Wiley and Sons 🌐 English βš– 115 KB πŸ‘ 1 views

This note can be treated a s a supplement to a paper written by Bollobas which was devoted to the vertices of a given degree in a random graph. We determine some values of the edge probability p for which the number of vertices of a given degree of a random graph G E ?An, p) asymptotically has a nor