On edge disjoint spanning trees in a randomly weighted complete graph

Abstract

Assume that the edges of the complete graph $K_n$ are given independent uniform $[0,1]$ edges weights. We consider the expected minimum total weight ${\mu }_k$ of $k\ge 2$ edge disjoint spanning trees. When $k$ is large we show that ${\mu }_k\approx k^2$. Most of the paper is concerned with the case $k=2$. We show that $\m_2$ tends to an explicitly defined constant and that ${\mu }_2\approx 4.1704288\dots$.

arXiv commentFixed minor issues