On Average Edge Length of Minimum Spanning Trees

Suman Kumar Nath, Rezaul Alam Chowdhury, and M. Kaykobad

Information Processing Letters, vol. 70 (5), pp. 241-243, 1999

This paper presents a theorem that asserts that average edge length of the minimum spanning tree of a complete graph on n + 1 vertices is less than or equal to the average edge length of all the n + 1 minimum spanning trees of the induced graph on n vertices. The result is also in compliance with results given by Frieze and Steele.

Download (copyright restrictions may apply): PSPDF