Abstract

In this dissertation, we are primarily concerned with exact formulae for the expected length of minimum spanning tree (MST) on finite connected graphs with random edge lengths. Based on tools associated with the multivariate Tutte polynomial, our general formula covers non-identically distributed edge lengths. This generalizes considerably the existing exact formulae in the literature.

As applications of these exact formulae in terms of the Tutte polynomials, we compare the expected length of minimum spanning tree under different edge weight distributions, in particular, uniform distribution on the interval (0,1) and exponential distribution with rate 1. For the complete graph and the complete graph with multiple edges, we determine the precise rate of convergence for the difference of the expected length of MST between these two distributions.

We provide in-depth study of the expected length of MST on specific families of graphs, which include wheel graphs, Fibonacci graphs and cylinder graphs with two types of edges. For these graphs, the Tutte polynomial or multivariate Tutte polynomial are computed explicitly. By applying our general formulae, the exact value and asymptotic behavior of the expected length of MST with non-identical edge distributions are studied. In addition, we make several observations on the complete graph.