Asymptotic Enumeration by Degree Sequence of Graphs of High Degree

Brendan D. McKay, Nicholas C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

66 Citations (Scopus)

Abstract

We consider the estimation of the number of labelled simple graphs with degree sequence d1, d2, . . . , dn by using an n-dimensional Cauchy integral. For sufficiently small ε and any c 〉 2/3, an asymptotic formula is obtained when |di − d| < n1/2 + ε for all i and d = d(ni) satisfies min{d, n − d − 1) ⩾ cn/log n as n→ ∞. These conditions include the degree sequences of almost all graphs, so our result gives as a corollary the asymptotic joint distribution function of the degrees of a random graph. We also give evidence for a formula conjectured to be valid for all d(n).

Original languageEnglish
Pages (from-to)565-580
Number of pages16
JournalEuropean Journal of Combinatorics
Volume11
Issue number6
DOIs
Publication statusPublished - 1990
Externally publishedYes

Cite this