Premium
Diameter of random spanning trees in a given graph
Author(s) -
Chung Fan,
Horn Paul,
Lu L.
Publication year - 2012
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/jgt.20577
Subject(s) - combinatorics , mathematics , spanning tree , random graph , graph , trémaux tree , discrete mathematics , line graph , pathwidth
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