Counting connected graphs asymptotically

Research output: Contribution to journalArticleAcademicpeer-review

19 Citations (Scopus)


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
Pages (from-to)1294-1320
JournalEuropean Journal of Combinatorics
Issue number8
Publication statusPublished - 2006


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

Cite this