Large deviation properties of minimum spanning trees for random graphs.

We study the large-deviation properties of minimum spanning trees for two ensembles of random graphs with N nodes. First, we consider complete graphs. Second, we study Erdős-Rényi (ER) random graphs with edge probability p=c/N conditioned on being connected. By using large-deviation Markov-chain sampling, we can obtain the distribution P(W) of the spanning-tree weight W down to probability densities as small as 10^{-300}. For the complete graph, we confirm analytical predictions with respect to the expectation value. For both ensembles, the large-deviation principle is fulfilled. For the connected ER graphs, we observe a remarkable change of the distributions at the value of c=1, which is the percolation threshold for the original ER ensemble.