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
Greenhill, C., Kwan, M., & Wind, D. K. (2014). On the number of spanning trees in random regular graphs. The Electronic Journal of Combinatorics, 21(1), [P1.45]. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p45