Counting Connected Graphs
Counting Connected Graphs
-
Joel Spencer, New York University
听Let C(n,k) be the number of labelled connected graphs with n vertices and n-1+k edges.听 For k=0 (trees) we have Cayley's Formula.听 We examine the asymptotics of C(n,k).听 There are several approaches involving supercritical dominant components in random graphs, local limit laws, Brownian excursions, Parking functions and other topics.