Consider the class of graphs on n vertices which have maximum degree at most 1/2n−1+τ, where τ ≥ −n1/2+e for sufficiently small e > 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.
['Brendan D. McKay', 'Ian M. Wanless', 'Nicholas C. Wormald']
Asymptotic Enumeration of Graphs with a Given Upper Bound on the Maximum Degree