Diameter of random spanning trees in a given graph |
| |
Authors: | Fan Chung Paul Horn L Lu |
| |
Institution: | 1. University of california, , San diego;2. Emory university, , Atlanta;3. University of south carolina, , South carolina |
| |
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 logn. Copyright © 2011 John Wiley Periodicals, Inc. J Graph Theory 69: 223–240, 2012 |
| |
Keywords: | spanning trees random walks |
|
|