Counting connected graphs asymptotically

Research output: Contribution to journalArticleAcademicpeer-review

20 Citations (Scopus)

Abstract

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
Volume27
Issue number8
DOIs
Publication statusPublished - 2006

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

Cite this