Abstract
We determine the asymptotic number of labelled graphs with a given degree sequence for the case where the maximum degree iso(|E(G)|1/3). The previously best enumeration, by the first author, required maximum degreeo(|E(G)|1/4). In particular, ifk=o(n 1/2), the number of regular graphs of degreek and ordern is asymptotically
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
B. D. McKay: Asymptotics for symmetric 0–1 matrices with prescribed row sums,Ars Combinatoria,19A (1985) 15–25.
B. D. McKay, andN. C. Wormald: Automorphisms of random graphs with specified degrees,Combinatorica,4 (1984) 325–338.
B. D. McKay, andN. C. Wormald: Asymptotic enumeration by degree sequence of graphs of high degree,European J. Combinatorics,11 (1990) 565–580.
B. D. McKay, andN. C. Wormald: Uniform generation of random regular graphs of moderate degree,J. Algorithms,11 (1990) 52–67.