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

Brendan D. McKay, Nicholas C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

118 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