pith. sign in

arxiv: 1505.03429 · v4 · pith:CNVIIWEFnew · submitted 2015-05-13 · 🧮 math.CO

On edge disjoint spanning trees in a randomly weighted complete graph

classification 🧮 math.CO
keywords approxcompletedisjointedgeedgesgraphspanningtrees
0
0 comments X
read the original 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\geq 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\ldots$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.