The expected value of random minimal length spanning tree of a complete graph

ABSTRACT

We consider the number c(n, m) of connected labeled graphs on n nodes and m edges and the intimately related object, the expected length of the minimal spanning tree of a complete graphs with random edge lengths. We use a very simple recursive procedure for computing the values of c(n, m) for computing the expected length of the minimal spanning tree exactly, under the uniform and the exponential distributions. Our computations are recursive, scale very well with the size of the problem, and we provide the values of the expected minimal length spanning trees for complete graphs Kn with sizes n ≤ 45, extending recent results of Steele [Ste02], and Fill and Steele [FS04]. The main proof technique is based on introducing an artificial root to a graph and subsequently using a very simple inductive argument.

REFERENCES

• 1: {AB92} F. Avram and D. Bertsimas, The minimum spanning tree constant in geometric probability and under the independent model: a unified approach, The Annals of Applied Probability 2 (1992), 113--130.
• 2: {BCM90} E. Bender, E. Canfield, and B. McKay, The asymptotic number of labeled connected graphs with a given number of vertices and edges, Random structures and algorithms 1 (1990), no. 2, 127--169.
• 3: {COMS04} A. Coja-Oghlan, C. Moore, and V. Sanwalani, Counting connected graphs and hypergraphs via the probabilistic method, Proceedings of RANDOM, 2004.
• 4: {Fri85} A. Frieze, On the value of a random minimum spanning tree problem, Discrete Appl. Math. 10 (1985), 47--56.
• 5: {FS04} J. Fill and M. Steele, Exact expectations of minimal spanning trees for graphs with random edge weights.
• 6: {GS96} I. Gessel and B. Sagan, The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions, Electronic J. Combinatorics, Foata Festschrift 3 (1996), no. 2, R9.
• 7: {HP73} F. Harary and E. M. Palmer, Graphical enumeration, Academic Press, 1973.
• 8: {Luc90} T. Luczak, On the number of sparse connected graphs, Random Structures and Algorithms 1 (1990), no. 2, 171--174.
• 9: J. M. Steele, On Frieze's &zgr;(3) limit for lengths of minimal spanning trees, Discrete Applied Mathematics, v.18 n.1, p.99-103, Nov. 1987 [doi>10.1016/0166-218X(87)90047-3]
• 10: {Ste02} J. M. Steele, On Minimal spanning trees for graphs with random edge lenghts, Mathematics and Computer Science II. Algorithms, Trees, Combinatorics and Probabilities, B. Chauvin, Ph. Flajolet, D. Gardy, and A. Mokkadem (eds.), Birkhäuser, Boston, 2002, pp. 223--245.