Counting connected graphs asymptotically

Remco van der Hofstad, Joel Spencer

Research output: Contribution to journalArticlepeer-review


We find the asymptotic number of connected graphs with k vertices and k - 1 + l edges when k, l approach infinity, re-proving a result of Bender, Canfield and McKay. We use the probabilistic method, analyzing breadth-first search on the random graph G (k, p) for an appropriate edge probability p. Central is the analysis of a random walk with fixed beginning and end which is tilted to the left.

Original languageEnglish (US)
Pages (from-to)1294-1320
Number of pages27
JournalEuropean Journal of Combinatorics
Issue number8 SPEC. ISS.
StatePublished - Nov 2006

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Counting connected graphs asymptotically'. Together they form a unique fingerprint.

Cite this