Asymptotic enumeration of sparse 2‐connected graphs

descriptionPublicationkeyboard_double_arrow_right Article , Preprint 04 Apr 2012Embargo end date: 01 Oct 2010 English Publisher:WileyJournal:Random Structures & Algorithms, volume 43, pages 354-376 (issn: 1042-9832, eissn: 1098-2418,

Copyright policy )Funded by:NSERC | unidentified

Authors: Graeme Kemkes; Cristiane M. Sato; Nicholas C. Wormald;

doi: 10.1002/rsa.20415 , 10.48550/arxiv.1010.2516

arXiv: 1010.2516

Asymptotic enumeration of sparse 2‐connected graphs

- Summary
- Subjects
- Metrics

Abstract

AbstractWe 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

Related Organizations

University of Waterloo
Canada
University of California, San Diego
United States
Toronto Metropolitan University
Canada
University of Waterloo (Canada)
Canada

Keywords

Connectivity, Random graphs (graph-theoretic aspects), Enumeration in graph theory, Asymptotic enumeration, asymptotic enumeration, FOS: Mathematics, Mathematics - Combinatorics, Density (toughness, etc.), Combinatorics (math.CO), 2-connected graphs, random graphs

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	2
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average