Asymptotic enumeration of sparse 2‐connected graphs |
| |
| Authors: | Graeme Kemkes Cristiane M Sato Nicholas Wormald |
| |
| Institution: | 1. Department of Mathematics, Ryerson University, Toronto, Ontario, Canada M5B 2K3This author's research was primarily carried out while at the University of California at San Diego under an NSERC postdoctoral award.;2. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1;3. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1Supported by the Canada Research Chairs Program and NSERC. |
| |
| Abstract: | We determine an asymptotic formula for the number of labelled 2‐connected (simple) graphs on n vertices and m edges, provided that m ‐ n →∞ and m = O(nlog n) as n →∞. This is the entire range of m not covered by previous results. The proof involves determining properties of the core and kernel of random graphs with minimum degree at least 2. The case of 2‐edge‐connectedness is treated similarly. We also obtain formulae for the number of 2‐connected graphs with given degree sequence for most (“typical”) sequences. Our main result solves a problem of Wright from 1983. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013 |
| |
| Keywords: | asymptotic enumeration 2‐connected graphs random graphs |
|
|
