Graph classes with given 3‐connected components: Asymptotic enumeration and random graphs1. Issue 4 (26th April 2012)

• Record Type: Journal Article
• Authors: Giménez, Omer; Noy, Marc; Rué, Juanjo
• Is Part Of: Random structures & algorithms. Volume 42:Issue 4(2013)
• Page Start: 438
• Page End: 479
• Publication Date: 2012-04-26
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20421
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>Consider a family <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\mathcal{T}\end{align*}\end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg20q1bjk9" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> of 3‐connected graphs of moderate growth, and let <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\mathcal{G}\end{align*}\end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg20q1bjjr" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> be the class of graphs whose 3‐connected components are graphs in <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\mathcal{T}\end{align*}\end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg20q1bjh6" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />. 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 <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\mathcal{G}\end{align*}\end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg20q1bjgn" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />, based on the singularities of the exponential generating function associated to <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\mathcal{T}\end{align*}\end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg20q1bjf3" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />. 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 was already observed by Panagiotou and Steger [<xref ref-type="link" rid="bib25">25</xref>], and we provide a finer description. For some classes under study both regimes occur, because of a critical phenomenon as the edge density in the class varies. Finally, we analyze the size of the largest 3‐connected component in random planar graphs. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 438–479, 2013</p> </abstract>