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

Catherine Greenhill, Mikhail Isaev, Matthew Kwan, Brendan D. McKay

    Research output: Contribution to journalArticlepeer-review

    16 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+12dmax4, 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

    Fingerprint

    Dive into the research topics of 'The average number of spanning trees in sparse graphs with given degrees'. Together they form a unique fingerprint.

    Cite this