Delphi.science

The Sum of Leaf Weights in the Minimum Spanning Tree of the Complete Graph

Source: arxiv.org/abs/2611.21540

Julia Gaudio, Phawin Prongpaophan, Miklós Z. Rácz

arXivarxiv/2611.21540Nov 16, 2026cs.DMscore 0

Let $G_n$ be a random weighted complete graph on $n$ vertices, where edges have i.i.d. $\text{Unif}(0,1)$ weights. Let $T_n$ be the Minimum Spanning Tree (MST) of $G_n$. The expected weight of $T_n$ is known to converge to $ζ(3) = \sum_{k=1}^{\infty} \frac{1}{k^3}$ (Frieze 1985). We investigate the sum of weights of edges incident to the leaves of $T_n$, denoting this quantity by $L_n$. We give tight upper and lower bounds on $\mathbb{E}[L_n]$ and determine its limit as $n$ diverges, leveraging typical behavior of sparse Erdős--Rényi random graphs. We also establish concentration of $L_n$…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.21540
curl -X POST /api/v1/records/arxiv/2611.21540/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.21540/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'