Asymptotic enumeration of sparse 2-connected graphs

DOI10.1002/RSA.20415zbMATH Open1273.05127OpenAlexW2592011129MaRDI QIDQ2856579FDOQ2856579

Authors: Graeme Kemkes, Cristiane M. Sato, Nicholas Wormald 

Publication date: 29 October 2013

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: We determine an asymptotic formula for the number of labelled 2-connected (simple) graphs on $n$ vertices and $m$ edges, provided that $m-noinfty$ and $m=O(nlogn)$ as $noinfty$. 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.

Full work available at URL: https://arxiv.org/abs/1010.2516

Recommendations

• Asymptotic enumeration of sparse graphs with a minimum degree constraint
• Asymptotic enumeration of sparse multigraphs with given degrees
• scientific article; zbMATH DE number 4075100
• On the number of sparse connected graphs
• Asymptotic enumeration of sparse uniform hypergraphs with given degrees
• Asymptotic enumeration of 2-covers and line graphs
• Asymptotic enumeration of full graphs
• Asymptotic enumeration of strongly connected digraphs by vertices and edges
• Asymptotic enumeration on self-similar graphs with two boundary vertices
• Asymptotic enumeration of cographs

zbMATH Keywords

random graphsasymptotic enumeration2-connected graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Asymptotic enumeration (05A16) Enumeration in graph theory (05C30) Connectivity (05C40) Density (toughness, etc.) (05C42)

Cites Work

• The number of connected sparsely edged graphs. II. Smooth graphs and blocks
• On the strength of connectedness of a random graph
• Asymptotic enumeration of sparse graphs with a minimum degree constraint
• Title not available (Why is that?)
• Forbidden subgraphs in connected graphs
• Counting connected graphs inside-out
• The asymptotic number of labeled connected graphs with a given number of vertices and edges
• The exponential generating function of labelled blocks
• On the Enumeration of Mayer Cluster Integrals
• The asymptotic number of labeled graphs with \(n\) vertices, \(q\) edges, and no isolated vertices
• On the number of graphs with a fixed number of vertices, edges, and isolated vertices
• The number of connected sparsely edged graphs. IV large nonseparable graphs

Cited In (16)

• Asymptotic enumeration of 2-covers and line graphs
• Title not available (Why is that?)
• Counting connected hypergraphs via the probabilistic method
• Title not available (Why is that?)
• Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees
• Counting strongly-connected, moderately sparse directed graphs
• Title not available (Why is that?)
• Asymptotic enumeration of sparse uniform hypergraphs with given degrees
• Title not available (Why is that?)
• Title not available (Why is that?)
• Counting connected graphs inside-out
• Asymptotic enumeration of sparse graphs with a minimum degree constraint
• Another proof of Wright's inequalities
• The asymptotic number of labeled connected graphs with a given number of vertices and edges
• Counting sparse \(k\)-edge-connected hypergraphs with given number of vertices and edges
• On the number of sparse connected graphs

This page was built for publication: Asymptotic enumeration of sparse 2-connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2856579)