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)

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

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)