Asymptotic enumeration by degree sequence of graphs with degrees o(n1/2)

Brendan D. McKay, Nicholas C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

109 Citations (Scopus)

Abstract

We determine the asymptotic number of labelled graphs with a given degree sequence for the case where the maximum degree is o(|E(G)|1/3). The previously best enumeration, by the first author, required maximum degree o(|E(G)|1/4). In particular, if k=o(n1/2), the number of regular graphs of degree k and order n is asymptotically {Mathematical expression} Under slightly stronger conditions, we also determine the asymptotic number of unlabelled graphs with a given degree sequence. The method used is a switching argument recently used by us to uniformly generate random graphs with given degree sequences.

Original languageEnglish
Pages (from-to)369-382
Number of pages14
JournalCombinatorica
Volume11
Issue number4
DOIs
Publication statusPublished - Dec 1991
Externally publishedYes

Keywords

  • AMS subject classification (1991): 05C30, 05C80

Cite this

@article{700f1c8449154e0c87753620a73a7a44,
title = "Asymptotic enumeration by degree sequence of graphs with degrees o(n1/2)",
abstract = "We determine the asymptotic number of labelled graphs with a given degree sequence for the case where the maximum degree is o(|E(G)|1/3). The previously best enumeration, by the first author, required maximum degree o(|E(G)|1/4). In particular, if k=o(n1/2), the number of regular graphs of degree k and order n is asymptotically {Mathematical expression} Under slightly stronger conditions, we also determine the asymptotic number of unlabelled graphs with a given degree sequence. The method used is a switching argument recently used by us to uniformly generate random graphs with given degree sequences.",
keywords = "AMS subject classification (1991): 05C30, 05C80",
author = "McKay, {Brendan D.} and Wormald, {Nicholas C.}",
year = "1991",
month = "12",
doi = "10.1007/BF01275671",
language = "English",
volume = "11",
pages = "369--382",
journal = "Combinatorica",
issn = "0209-9683",
publisher = "Springer-Verlag London Ltd.",
number = "4",

}

Asymptotic enumeration by degree sequence of graphs with degrees o(n1/2). / McKay, Brendan D.; Wormald, Nicholas C.

In: Combinatorica, Vol. 11, No. 4, 12.1991, p. 369-382.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Asymptotic enumeration by degree sequence of graphs with degrees o(n1/2)

AU - McKay, Brendan D.

AU - Wormald, Nicholas C.

PY - 1991/12

Y1 - 1991/12

N2 - We determine the asymptotic number of labelled graphs with a given degree sequence for the case where the maximum degree is o(|E(G)|1/3). The previously best enumeration, by the first author, required maximum degree o(|E(G)|1/4). In particular, if k=o(n1/2), the number of regular graphs of degree k and order n is asymptotically {Mathematical expression} Under slightly stronger conditions, we also determine the asymptotic number of unlabelled graphs with a given degree sequence. The method used is a switching argument recently used by us to uniformly generate random graphs with given degree sequences.

AB - We determine the asymptotic number of labelled graphs with a given degree sequence for the case where the maximum degree is o(|E(G)|1/3). The previously best enumeration, by the first author, required maximum degree o(|E(G)|1/4). In particular, if k=o(n1/2), the number of regular graphs of degree k and order n is asymptotically {Mathematical expression} Under slightly stronger conditions, we also determine the asymptotic number of unlabelled graphs with a given degree sequence. The method used is a switching argument recently used by us to uniformly generate random graphs with given degree sequences.

KW - AMS subject classification (1991): 05C30, 05C80

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

U2 - 10.1007/BF01275671

DO - 10.1007/BF01275671

M3 - Article

VL - 11

SP - 369

EP - 382

JO - Combinatorica

JF - Combinatorica

SN - 0209-9683

IS - 4

ER -