file.pdf (372.27 kB)

# On the length of a random minimum spanning tree

journal contribution
posted on 09.03.2013, 00:00 by Colin Cooper, Nate Ince, Svante Janson, Joel Spencer

We study the expected value of the length Ln of the minimum spanning tree of the complete graph Kn when each edge e is given an independent uniform [0,1] edge weight. We sharpen the result of Frieze \cite{F1} that $\lim_{n\to\infty}\E(L_n)=\z(3)$ and show that$\E(L_n)=\z(3)+\frac{c_1}{n}+\frac{c_2+o(1)}{n^{4/3}}$ where c1,c2 are explicitly defined constants.

09/03/2013

## Exports

figshare. credit for all your research.