2026-04-13T00:13:14Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/1085982026-01-27T04:29:55Zcom_2072_1033col_2072_452950

urn:hdl:2117/108598 Subgraph statistics in subcritical graph classes Drmota, Michael Ramos Garrido, Lander Rué Perna, Juan José Àrees temàtiques de la UPC::Matemàtiques i estadística Combinatorial analysis analytic combinatorics generating functions random graphs subcritical graph classes series-parallel graphs Anàlisi combinatòria Let H be a fixed graph and math formula a subcritical graph class. In this paper we show that the number of occurrences of H (as a subgraph) in a graph in math formula 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. Postprint (author's final draft) 2017-04-01 Article http://onlinelibrary.wiley.com/doi/10.1002/rsa.20721/abstract info:eu-repo/grantAgreement/EC/FP7/630749/EU/Enumeration of discrete structures: algebraic, analytic, probabilistic and algorithmic methods for enriched planar graphs and planar maps/COUNTGRAPH Open Access