Answers are grounded in this paper and cite their sources.
Let Gₙ be a random weighted complete graph on n vertices, where edges have i.i.d. Unif(0,1) weights. Let Tₙ be the Minimum Spanning Tree (MST) of Gₙ. The expected weight of Tₙ is known to converge to ζ(3) = ∑ₖ₌₁∞ 1/k³ (Frieze 1985). We investigate the sum of weights of edges incident to the leaves of Tₙ, denoting this quantity by Lₙ. We give tight upper and lower bounds on E[Lₙ] and determine its limit as n diverges, leveraging typical behavior of sparse Erdős--Rényi random graphs. We also establish concentration of Lₙ around E[Lₙ] 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).
No takes yet. Share an insight, caveat, or question.
Gaudio et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: