Skip navigation
Skip navigation

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

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


We give an asymptotic expression for the expected number of spanning trees in a random graph with a given degree sequence d = (d₁, . . . , dn), provided that the number of edges is at least n + 1/2d⁴max, 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.

CollectionsANU Research Publications
Date published: 2017-06
Type: Journal article
Source: European Journal of Combinatorics
DOI: 10.1016/j.ejc.2017.02.003
Access Rights: Open Access


File Description SizeFormat Image
01 Greenhill et al The average number 2017.pdf240.71 kBAdobe PDFThumbnail

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator