Minimal Spanning Trees for Graphs With Random Edge Lengths

The theory of the minimal spanning tree (MST) of a connected graph whose edges are assigned lengths according to independent identically distributed random variables is developed from two directions. First, it is shown how the Tutte polynomial for a connected graph can be used to provide an exact formula for the length of the minimal spanning tree under the model of uniformly distributed edge lengths. Second, it is shown how the theory of local weak convergence provides a systematic approach to the asymptotic theory of the length of the MST and related power sums. Consequences of these investigations include (1) the exact rational determination of the expected length of the MST for the complete graph Kn for 2 ≤ n ≤ 9 and (2) refinements of the results of Penrose (1998) for the MST of the d-cube and results of Beveridge, Frieze, and McDiarmid (1998) and Frieze, Ruzink6, and Thoma (2000) for graphs with modest expansion properties. In most cases, the results reviewed here have not reached their final form, and they should be viewed as part of work-in-progress