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.

Description

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
URI: http://hdl.handle.net/1885/114488
Source: European Journal of Combinatorics
DOI: 10.1016/j.ejc.2017.02.003
Access Rights: Open Access

Download

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:  22 January 2019/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator