On the number of spanning trees in random regular graphs

Abstract

Let $d\ge 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\to \infty$, 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.

26 pages, 1 figure. To appear in the Electronic Journal of Combinatorics. This version addresses referee's comments

Cited by in corpus (1)

• Spanning trees in random regular uniform hypergraphs