The average number of spanning trees in sparse graphs with given degrees

Abstract

We give an asymptotic expression for the expected number of spanning trees in a random graph with a given degree sequence $\mathbf{d}=(d_1,\dots ,d_n)$, provided that the number of edges is at least $n+\frac{1}{2}{d}_{\max }^4$, where $d_{\max }$ is the maximum degree. A key part of our argument involves establishing a concentration result for a certain family of functions over random trees with given degrees, using Prüfer codes.

24 pages, 1 figure. This version fixes some minor errors