ASYMPTOTIC ENUMERATION BY DEGREE SEQUENCE OF GRAPHS WITH DEGREES O(N1/2)

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 (nk)!/(nk/2)!2nk/2(k!)n exp(-k2-1/4 - k3/12n + O(k2/n)). 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.