Asymptotic enumeration of graphs with a given upper bound on the maximum degree

Brendan D. McKay; Ian M. Wanless; Nicholas C. Wormald

doi:10.1017/S0963548302005229

Asymptotic enumeration of graphs with a given upper bound on the maximum degree

Brendan D. McKay^*, Ian M. Wanless, Nicholas C. Wormald

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

Abstract

Consider the class of graphs on n vertices which have maximum degree at most 1/2 n - 1 + τ, where τ ≥ - n^1/2+ε for sufficiently small ε > 0. We find an asymptotic formula for the number of such graphs and show that their number of edges has a normal distribution whose parameters we determine. We also show that expectations of random variables on the degree sequences of such graphs can often be estimated using a model based on truncated binomial distributions.

Original language	English
Pages (from-to)	373-392
Number of pages	20
Journal	Combinatorics Probability and Computing
Volume	11
Issue number	4
DOIs	https://doi.org/10.1017/S0963548302005229
Publication status	Published - Jul 2002

Access to Document

10.1017/S0963548302005229

Cite this

@article{e4fa325f5f094ce58c310bfc0a4e2902,

title = "Asymptotic enumeration of graphs with a given upper bound on the maximum degree",

abstract = "Consider the class of graphs on n vertices which have maximum degree at most 1/2 n - 1 + τ, where τ ≥ - n1/2+ε for sufficiently small ε > 0. We find an asymptotic formula for the number of such graphs and show that their number of edges has a normal distribution whose parameters we determine. We also show that expectations of random variables on the degree sequences of such graphs can often be estimated using a model based on truncated binomial distributions.",

author = "McKay, {Brendan D.} and Wanless, {Ian M.} and Wormald, {Nicholas C.}",

year = "2002",

month = jul,

doi = "10.1017/S0963548302005229",

language = "English",

volume = "11",

pages = "373--392",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "4",

}

TY - JOUR

T1 - Asymptotic enumeration of graphs with a given upper bound on the maximum degree

AU - McKay, Brendan D.

AU - Wanless, Ian M.

AU - Wormald, Nicholas C.

PY - 2002/7

Y1 - 2002/7

N2 - Consider the class of graphs on n vertices which have maximum degree at most 1/2 n - 1 + τ, where τ ≥ - n1/2+ε for sufficiently small ε > 0. We find an asymptotic formula for the number of such graphs and show that their number of edges has a normal distribution whose parameters we determine. We also show that expectations of random variables on the degree sequences of such graphs can often be estimated using a model based on truncated binomial distributions.

AB - Consider the class of graphs on n vertices which have maximum degree at most 1/2 n - 1 + τ, where τ ≥ - n1/2+ε for sufficiently small ε > 0. We find an asymptotic formula for the number of such graphs and show that their number of edges has a normal distribution whose parameters we determine. We also show that expectations of random variables on the degree sequences of such graphs can often be estimated using a model based on truncated binomial distributions.

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

U2 - 10.1017/S0963548302005229

DO - 10.1017/S0963548302005229

M3 - Article

SN - 0963-5483

VL - 11

SP - 373

EP - 392

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 4

ER -

Asymptotic enumeration of graphs with a given upper bound on the maximum degree

Abstract

Access to Document

Other files and links

Fingerprint

Cite this