The Diameter of the Minimum Spanning Tree of a Complete Graph
Louigi Addario-Berry, Nicolas Broutin, Bruce Reed
Abstract
Let {X1,…,Xn&choose;2} be independent identically distributed weights for the edges of Kn. If Xi ≠Xj for i ≠j, then there exists a unique minimum weight spanning tree T of Kn with these edge weights. We show that the expected diameter of T is Θ(n1/3). This settles a question of [Frieze97].
Full Text: PDF