Counting connected graphs asymptotically

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

19 Citaten (Scopus)

Samenvatting

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.
Originele taal-2Engels
Pagina's (van-tot)1294-1320
TijdschriftEuropean Journal of Combinatorics
Volume27
Nummer van het tijdschrift8
DOI's
StatusGepubliceerd - 2006

Vingerafdruk

Duik in de onderzoeksthema's van 'Counting connected graphs asymptotically'. Samen vormen ze een unieke vingerafdruk.

Citeer dit