Subgraph statistics in subcritical graph classes |
| |
| Authors: | Michael Drmota Lander Ramos Juanjo Rué |
| |
| Affiliation: | 1. Technische Univerisit?t Wien Wien, Institute of Discrete Mathematics and Geometry, Wiedner Hauptstrasse 810, Wien, Austria;2. Departament de Matemàtiques, Universitat Politècnica de Catalunya, Barcelona, Spain;3. Barcelona Graduate School of Mathematics, Campus de Bellaterra, Edifici C, Bellaterra, Barcelona, Spain |
| |
| Abstract: | Let H be a fixed graph and  a subcritical graph class. In this paper we show that the number of occurrences of H (as a subgraph) in a graph in  of order n, chosen uniformly at random, follows a normal limiting distribution with linear expectation and variance. The main ingredient in our proof is the analytic framework developed by Drmota, Gittenberger and Morgenbesser to deal with infinite systems of functional equations [Drmota, Gittenberger, and Morgenbesser, Submitted]. As a case study, we obtain explicit expressions for the number of triangles and cycles of length 4 in the family of series‐parallel graphs. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 631–673, 2017 |
| |
| Keywords: | analytic combinatorics generating functions random graphs subcritical graph classes series‐parallel graphs |
|
|
a subcritical graph class. In this paper we show that the number of occurrences of H (as a subgraph) in a graph in 
of order n, chosen uniformly at random, follows a normal limiting distribution with linear expectation and variance. The main ingredient in our proof is the analytic framework developed by Drmota, Gittenberger and Morgenbesser to deal with infinite systems of functional equations [Drmota, Gittenberger, and Morgenbesser, Submitted]. As a case study, we obtain explicit expressions for the number of triangles and cycles of length 4 in the family of series‐parallel graphs. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 631–673, 2017