### 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(n^{1/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 language | English |
---|---|

Pages (from-to) | 369-382 |

Number of pages | 14 |

Journal | Combinatorica |

Volume | 11 |

Issue number | 4 |

DOIs | |

Publication status | Published - Dec 1991 |

Externally published | Yes |

### Keywords

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

### Cite this

^{1/2}).

*Combinatorica*,

*11*(4), 369-382. https://doi.org/10.1007/BF01275671

}

^{1/2})',

*Combinatorica*, vol. 11, no. 4, pp. 369-382. https://doi.org/10.1007/BF01275671

**Asymptotic enumeration by degree sequence of graphs with degrees o(n ^{1/2}).** / McKay, Brendan D.; Wormald, Nicholas C.

Research output: Contribution to journal › Article › Research › peer-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 -

^{1/2}). Combinatorica. 1991 Dec;11(4):369-382. https://doi.org/10.1007/BF01275671