The average number of spanning trees in sparse graphs with given degrees
We give an asymptotic expression for the expected number of spanning trees in a random graph with a given degree sequence d = (d₁, . . . , dn), provided that the number of edges is at least n + 1/2d⁴max, where dmax 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.
|Collections||ANU Research Publications|
|Source:||European Journal of Combinatorics|
|01 Greenhill et al The average number 2017.pdf||240.71 kB||Adobe PDF||Request a copy|
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.