Random Minimum Length Spanning Trees in Regular Graphs
Published in Combinatorica, 1998
A. Beveridge, A. Frieze and C. McDiarmid, Random Minimum Length Spanning Trees in Regular Graphs, Combinatorica 18 (1998), 311-333.
Preprint link: https://github.com/mathbeveridge/mathbeveridge.github.io/blob/master/files/span.pdf
Consider a connected $r$-regular graph $G$ with random independent edge length, each uniformly distributed on $(0,1)$. Let $mst(G)$ be the expected length of a minimum spanning tree. We show that $mst(G)$ can be estimated quite accurately under two distinct circumstances.