The average number of spanning trees in sparse graphs with given degrees

Catherine Greenhill, Mikhail Isaev, Matthew Kwan, Brendan Damien McKay

Research output: Contribution to journalArticleResearchpeer-review

3 Citations (Scopus)

Abstract

We give an asymptotic expression for the expected number of spanning trees in a random graph with a given degree sequence d=(d1,…,dn), provided that the number of edges is at least n+12dmax 4, where dmax is the maximum degree. A key part of our argument involves establishing a concentration result for a certain family of functions over random trees with given degrees, using Prüfer codes.

Original languageEnglish
Pages (from-to)6-25
Number of pages20
JournalEuropean Journal of Combinatorics
Volume63
DOIs
Publication statusPublished - 1 Jun 2017
Externally publishedYes

Keywords

  • Tree
  • Continuum random
  • Random

Cite this