On the number of spanning trees in random regular graphs

Catherine Greenhill, Matthew Kwan, David Kofoed Wind

Research output: Contribution to journalJournal articleResearchpeer-review

119 Downloads (Pure)

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 languageEnglish
Article numberP1.45
JournalThe Electronic Journal of Combinatorics
Volume21
Issue number1
Number of pages26
ISSN1097-1440
Publication statusPublished - 2014

Keywords

  • Spanning trees
  • Random regular graphs
  • Small subgraph conditioning

Cite this