Greenhill, Catherine3; Kwan, Matthew3; Wind, David Kofoed1
1 Department of Applied Mathematics and Computer Science, Technical University of Denmark2 Cognitive Systems, Department of Applied Mathematics and Computer Science, Technical University of Denmark3 University of New South Wales
Let d >= 3 be a fixed integer. We give an asympotic formula for the expected number of spanning trees in a uniformly random d-regular graph with n vertices. (The asymptotics are as n -> infinity, restricted to even n if d is odd.) We also obtain the asymptotic distribution of the number of spanning trees in a uniformly random cubic graph, and conjecture that the corresponding result holds for arbitrary (fixed) d. Numerical evidence is presented which supports our conjecture.
Electronic Journal of Combinatorics, 2014, Vol 21, Issue 1
Spanning trees; Random regular graphs; Small subgraph conditioning