Subgraph statistics in subcritical graph classes

DOI10.1002/RSA.20721MaRDI QIDQ4597604zbMATH OpenOpenAlexFDO

Authors Michael Drmota, Lander Ramos, Juanjo Rué

Publication date 13 December 2017

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

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

zbMATH Keywords

generating functionsrandom graphsanalytic combinatoricssubcritical graph classesseries-parallel graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: Let $H$ be a fixed graph and $mathcalG$ a subcritical graph class. In this paper we show that the number of occurrences of $H$ (as a subgraph) in a uniformly at random graph of size $n$ in $mathcalG$ 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. As a case study, we get explicit expressions for the number of triangles and cycles of length four for the family of series-parallel graphs.

Recommendations

• Asymptotic study of subcritical graph classes
• The degree sequence of random graphs from subcritical classes
• Distribution of subgraphs of random regular graphs
• Subgraph counts in random graphs using incomplete U-statistics methods
• scientific article; zbMATH DE number 3865331

Cited in

(16)

• Enumeration of rooted 3-connected bipartite planar maps
• Limits of random tree-like discrete structures
• Asymptotic properties of random unlabelled block-weighted graphs
• The degree sequence of random graphs from subcritical classes
• Asymptotic study of subcritical graph classes
• Enumeration of chordal planar graphs and maps
• Subcritical graph classes containing all planar graphs
• scientific article; zbMATH DE number 4164910 (Why is no real title available?)
• Encoding and avoiding 2-connected patterns in polygon dissections and outerplanar graphs
• Maximal independent sets and maximal matchings in series-parallel and related graph classes
• On general subtrees of a conditioned Galton-Watson tree
• Threshold functions for small subgraphs: an analytic approach
• The complexity of the Approximate Multiple Pattern Matching Problem for random strings
• Threshold functions for small subgraphs in simple graphs and multigraphs
• Counting embeddings of rooted trees into families of rooted trees
• The h-Index of a Graph and its Application to Dynamic Subgraph Statistics

This page was built for publication: Subgraph statistics in subcritical graph classes

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