# On the number of spanning trees in random regular graphs

Catherine Greenhill, Matthew Kwan, David Kofoed Wind

Research output: Contribution to journalJournal articleResearchpeer-review

### Abstract

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.
Original language English P1.45 The Electronic Journal of Combinatorics 21 1 26 1097-1440 Published - 2014

### Keywords

• Spanning trees
• Random regular graphs
• Small subgraph conditioning

### Cite this

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].
Greenhill, Catherine ; Kwan, Matthew ; Wind, David Kofoed. / On the number of spanning trees in random regular graphs. In: The Electronic Journal of Combinatorics. 2014 ; Vol. 21, No. 1.
@article{10dc56bc817142d39daf60d36333b155,
title = "On the number of spanning trees in random regular graphs",
abstract = "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.",
keywords = "Spanning trees, Random regular graphs, Small subgraph conditioning",
author = "Catherine Greenhill and Matthew Kwan and Wind, {David Kofoed}",
year = "2014",
language = "English",
volume = "21",
journal = "The Electronic Journal of Combinatorics",
issn = "1097-1440",
publisher = "American Mathematical Society",
number = "1",

}

Greenhill, C, Kwan, M & Wind, DK 2014, 'On the number of spanning trees in random regular graphs', The Electronic Journal of Combinatorics, vol. 21, no. 1, P1.45.

On the number of spanning trees in random regular graphs. / Greenhill, Catherine; Kwan, Matthew; Wind, David Kofoed.

In: The Electronic Journal of Combinatorics, Vol. 21, No. 1, P1.45, 2014.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - On the number of spanning trees in random regular graphs

AU - Greenhill, Catherine

AU - Kwan, Matthew

AU - Wind, David Kofoed

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - Spanning trees

KW - Random regular graphs

KW - Small subgraph conditioning

M3 - Journal article

VL - 21

JO - The Electronic Journal of Combinatorics

JF - The Electronic Journal of Combinatorics

SN - 1097-1440

IS - 1

M1 - P1.45

ER -