Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-12T06:34:57.901Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic Enumeration of Graphs with a Given Upper Bound on the Maximum Degree

Published online by Cambridge University Press:  06 September 2002

BRENDAN D. McKAY ,
IAN M. WANLESS  and
NICHOLAS C. WORMALD
BRENDAN D. McKAY
Affiliation:
Department of Computer Science, Australian National University, Canberra, ACT 0200, Australia (e-mail: [email protected])
IAN M. WANLESS
Affiliation:
Christ Church, Oxford OX1 1DP, England (e-mail: [email protected])
NICHOLAS C. WORMALD
Affiliation:
Department of Mathematics and Statistics, University of Melbourne, Parkville, Vic 3052, Australia (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Consider the class of graphs on n vertices which have maximum degree at most 1/2n−1+τ, where τ [ges ] −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.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 11 , Issue 4 , July 2002 , pp. 373 - 392
Copyright
2002 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)