Graph classes with given 3-connected components: asymptotic enumeration and random graphs

DOI10.1002/RSA.20421MaRDI QIDQ2841679zbMATH OpenOpenAlexFDO

Authors Omer Giménez, Marc Noy, Juanjo Rué

Publication date 26 July 2013

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

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

zbMATH Keywords

asymptotic enumerationgraph minorsgraph parametersplanar graphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Random graphs (graph-theoretic aspects) (05C80) Graph minors (05C83)

Abstract: Consider a family $mathcalT$ of 3-connected graphs of moderate growth, and let $mathcalG$ be the class of graphs whose 3-connected components are graphs in $mathcalT$. We present a general framework for analyzing such graphs classes based on singularity analysis of generating functions, which generalizes previously studied cases such as planar graphs and series-parallel graphs. We provide a general result for the asymptotic number of graphs in $mathcalG$, based on the singularities of the exponential generating function associated to $mathcalT$. We derive limit laws, which are either normal or Poisson, for several basic parameters, including the number of edges, number of blocks and number of components. For the size of the largest block we find a fundamental dichotomy: classes similar to planar graphs have almost surely a unique block of linear size, while classes similar to series-parallel graphs have only sublinear blocks. This dichotomy also applies to the size of the largest 3-connected component. For some classes under study both regimes occur, because of a critical phenomenon as the edge density in the class varies.

Recommendations

• Graph classes with given 3-connected components: asymptotic counting and critical phenomena
• Maximal biconnected subgraphs of random planar graphs
• Asymptotic Properties of Some Minor-Closed Classes of Graphs
• Asymptotic properties of some minor-closed classes of graphs
• Asymptotic Enumeration of Graph Classes with Many Components

Cites work

• 3-Connected Cores In Random Planar Graphs
• A Census of Planar Triangulations
• A complete grammar for decomposing a family of graphs into 3-connected components
• Asymptotic enumeration and limit laws for graphs of fixed genus
• Asymptotic enumeration and limit laws of planar graphs
• Asymptotic enumeration of labelled graphs by genus
• Asymptotic study of subcritical graph classes
• Counting labelled three-connected and homeomorphically irreducible two- connected graphs
• Degree distribution in random planar graphs
• Enumeration and limit laws for series-parallel graphs
• Graph minors. XX: Wagner's conjecture
• Growth constants of minor-closed classes of graphs
• scientific article; zbMATH DE number 48089 (Why is no real title available?)
• Maximal biconnected subgraphs of random planar graphs
• Random cubic planar graphs
• Random graphs from a minor-closed class
• Random graphs on surfaces
• Random maps, coalescing saddles, singularity analysis, and Airy phenomena
• Random planar graphs
• Structure and enumeration of two-connected graphs with prescribed three-connected components
• The degree sequence of random graphs from subcritical classes
• The maximum degree of series-parallel graphs
• The Size of the Largest Components in Random Planar Maps

Cited in

(35)

• Random enriched trees with applications to random graphs
• Logical limit laws for minor-closed classes of graphs
• Encoding and avoiding 2-connected patterns in polygon dissections and outerplanar graphs
• On the sum of digits of some sequences of integers
• Random planar maps and graphs with minimum degree two and three
• Enumeration of chordal planar graphs and maps
• Quenched local convergence of Boltzmann planar maps
• Limits of random tree-like discrete structures
• On the maximal offspring in a subcritical branching process
• Maximal independent sets and maximal matchings in series-parallel and related graph classes
• Multi-critical behaviour of 4-dimensional tensor models up to order 6
• Asymptotic enumeration and limit laws for graphs of fixed genus
• Spanning trees in random series-parallel graphs
• Maximum degree in minor-closed classes of graphs
• Local convergence of random planar graphs
• Enumeration of labelled 4-regular planar graphs. II: Asymptotics
• The maximum degree of random planar graphs
• 3-Connected Cores In Random Planar Graphs
• Asymptotic Properties of Some Minor-Closed Classes of Graphs
• Triangles in random cubic planar graphs
• Graph classes with given 3-connected components: asymptotic counting and critical phenomena
• On zero-one and convergence laws for graphs embeddable on a fixed surface
• Asymptotic Enumeration of Graph Classes with Many Components
• Expected Maximum Block Size in Critical Random Graphs
• On the diameter of random planar graphs
• On the probability of planarity of a random graph near the critical point
• The maximum degree of random planar graphs
• Asymptotic properties of some minor-closed classes of graphs
• Longest and shortest cycles in random planar graphs
• Random graphs: combinatorics, complex networks and disordered systems. Abstracts from the workshop held March 26--31, 2023
• Local convergence of random planar graphs
• Phase transitions of composition schemes: Mittag-Leffler and mixed Poisson distributions
• The uniform infinite cubic planar graph
• The scaling limit of random cubic planar graphs
• Random graphs from a block-stable class

This page was built for publication: Graph classes with given 3-connected components: asymptotic enumeration and random graphs

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