The average number of spanning trees in sparse graphs with given degrees
Date
2017-06
Authors
Greenhill, Catherine
Isaev, Mikhail
Kwan, Matthew
McKay, Brendan D.
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Abstract
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.
Description
Keywords
asymptotic, expression, random, graph, Prüfer, codes
Citation
Collections
Source
European Journal of Combinatorics
Type
Journal article
Book Title
Entity type
Access Statement
Open Access
License Rights
Restricted until
Downloads
File
Description