Premium
Asymptotic enumeration of sparse 2‐connected graphs
Author(s) -
Kemkes Graeme,
Sato Cristiane M.,
Wormald Nicholas
Publication year - 2013
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20415
Subject(s) - combinatorics , mathematics , enumeration , social connectedness , degree (music) , sequence (biology) , simple (philosophy) , discrete mathematics , kernel (algebra) , wright , struct , computer science , physics , biology , psychology , philosophy , epistemology , acoustics , psychotherapist , genetics , programming language
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 ( n log 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