2010/10/12 by Graeme Kemkes, Kemkes, Graeme, Cristiane M. Sato +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1010.2516
openalex publication_date 2010/10/12 · arxiv created 2011/05/25 · arxiv updated 2011/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.