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.
|Journal||The Electronic Journal of Combinatorics|
|Number of pages||26|
|Publication status||Published - 2014|
- Spanning trees
- Random regular graphs
- Small subgraph conditioning