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

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

doi:10.1016/j.ejc.2017.02.003

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 journal › Article › peer-review

18 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=(d₁,…,d_n), provided that the number of edges is at least n+12d_max⁴, where d_max 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 language	English
Pages (from-to)	6-25
Number of pages	20
Journal	European Journal of Combinatorics
Volume	63
DOIs	https://doi.org/10.1016/j.ejc.2017.02.003
Publication status	Published - 1 Jun 2017

Access to Document

10.1016/j.ejc.2017.02.003

Cite this

@article{0c22bd31f13644869bf00c61be250045,

title = "The average number of spanning trees in sparse graphs with given degrees",

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{\"u}fer codes.",

author = "Catherine Greenhill and Mikhail Isaev and Matthew Kwan and McKay, {Brendan D.}",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier Ltd",

year = "2017",

month = jun,

day = "1",

doi = "10.1016/j.ejc.2017.02.003",

language = "English",

volume = "63",

pages = "6--25",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

}

TY - JOUR

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

AU - Greenhill, Catherine

AU - Isaev, Mikhail

AU - Kwan, Matthew

AU - McKay, Brendan D.

PY - 2017/6/1

Y1 - 2017/6/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85014749818&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2017.02.003

DO - 10.1016/j.ejc.2017.02.003

M3 - Article

SN - 0195-6698

VL - 63

SP - 6

EP - 25

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

ER -

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

Abstract

Access to Document

Other files and links

Fingerprint

Cite this