Asymptotic enumeration of sparse graphs with a minimum degree constraint

doi:10.1016/S0097-3165(02)00017-1

Journal of Combinatorial Theory, Series A

Volume 101, Issue 2, February 2003, Pages 249-263

Asymptotic enumeration of sparse graphs with a minimum degree constraint

https://doi.org/10.1016/S0097-3165(02)00017-1 Get rights and content

Under an Elsevier user license

open archive

Abstract

We derive an asymptotic formula for the number of graphs with n vertices all of degree at least k, and m edges, with k fixed. This is done by summing the asymptotic formula for the number of graphs with a given degree sequence, all degrees at least k. This approach requires analysis of a set of independent truncated Poisson variables, which approximate the degree sequence of a random graph chosen uniformly at random among all graphs with n vertices, m edges, and a minimum degree at least k. Our main result generalizes a result of Bender, Canfield and McKay and of Korshunov, who treated the case k=1 using different methods.

¹: Research supported by the NSF Grant DMS-0104104.

²: Research supported by the Australian Research Council. Current address: Department of Combinatorics and Optimization, University of Waterloo, Waterloo ON, Canada N2L 3G1.