A Note on Random Minimum Length Spanning Trees

Abstract

Consider a connected $r$-regular $n$-vertex graph $G$ with random independent edge lengths, each uniformly distributed on $[0,1]$. Let $mst(G)$ be the expected length of a minimum spanning tree. We show in this paper that if $G$ is sufficiently highly edge connected then the expected length of a minimum spanning tree is $\sim {n\over r}\zeta(3)$. If we omit the edge connectivity condition, then it is at most $\sim {n\over r}(\zeta(3)+1)$.