Hostname: page-component-6898cfcb55-zsp5v Total loading time: 0 Render date: 2026-11-11T11:02:29.609Z Has data issue: false hasContentIssue false

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
Affiliation:
Department of Computer Science, Australian National University, Canberra, ACT 0200, Australia (e-mail: bdm@cs.anu.edu.au)
IAN M. WANLESS
Affiliation:
Christ Church, Oxford OX1 1DP, England (e-mail: wanless@maths.ox.ac.uk)
NICHOLAS C. WORMALD
Affiliation:
Department of Mathematics and Statistics, University of Melbourne, Parkville, Vic 3052, Australia (e-mail: nick@ms.unimelb.edu.au)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
2002 Cambridge University Press