TY - JOUR
T1 - Counting connected graphs asymptotically
AU - van der Hofstad, Remco
AU - Spencer, Joel
N1 - Funding Information:
This project was initiated during visits of both authors to Microsoft Research in July 2004. We thank Benny Sudakov and Michael Krivelevich for useful discussions at the start of this project. JS thanks Nitin Arora for help with the asymptotics of . The work of RvdH was supported in part by the Netherlands Organisation for Scientific Research (NWO), and was performed in part while visiting the Mittag-Leffler Institute in November 2004.
PY - 2006/11
Y1 - 2006/11
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=33748573619&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33748573619&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2006.05.006
DO - 10.1016/j.ejc.2006.05.006
M3 - Article
AN - SCOPUS:33748573619
SN - 0195-6698
VL - 27
SP - 1294
EP - 1320
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
IS - 8 SPEC. ISS.
ER -