WorksComputer Science
The Sum of Leaf Weights in the Minimum Spanning Tree of the Complete Graph
Abstract
Let be a random weighted complete graph on vertices, where edges have i.i.d. weights. Let be the Minimum Spanning Tree (MST) of . The expected weight of is known to converge to (Frieze 1985). We investigate the sum of weights of edges incident to the leaves of , denoting this quantity by . We give tight upper and lower bounds on and determine its limit as diverges, leveraging typical behavior of sparse Erdős–Rényi random graphs. We also establish concentration of around and almost sure convergence to this value. These results directly yield substantial improvements to state-of-the-art bounds for two important variants of the MST problem: (1) an improved upper bound on the weight of the optimal random instance Steiner tree, as studied by Bollobás, Gamarnik, Riordan, and Sudakov (2004); and (2) an improvement over the upper bound for the Probabilistic Minimum Spanning Tree, introduced by Bertsimas (1988).