Asymptotic enumeration of sparse 2‐connected graphs. Issue 3 (4th April 2012)

• Record Type: Journal Article
• Authors: Kemkes, Graeme; Sato, Cristiane M.; Wormald, Nicholas
• Is Part Of: Random structures & algorithms. Volume 43:Issue 3(2013)
• Page Start: 354
• Page End: 376
• Publication Date: 2012-04-04
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20415
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>We determine an asymptotic formula for the number of labelled 2‐connected (simple) graphs on <italic>n</italic> vertices and <italic>m</italic> edges, provided that <italic>m</italic> ‐ <italic>n</italic> →<italic>∞</italic> and <italic>m</italic> = <italic>O</italic>(<italic>n</italic>log <italic>n</italic>) as <italic>n</italic> →<italic>∞</italic>. This is the entire range of <italic>m</italic> 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</p> </abstract>