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


File Description SizeFormat Image
01 Greenhill et al The average number 2017.pdf240.71 kBAdobe PDF    Request a copy

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

Updated:  20 July 2017/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator