Subgraph statistics in subcritical graph classes

DOI10.1002/RSA.20721zbMATH Open1379.05100arXiv1512.08889OpenAlexW3102103241MaRDI QIDQ4597604FDOQ4597604

Juanjo Rué, Lander Ramos, Michael Drmota

Publication date: 13 December 2017

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

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.

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

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 Keywords

generating functionsrandom graphsanalytic combinatoricssubcritical graph classesseries-parallel graphs

Mathematics Subject Classification ID

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

Cited In (14)

• Enumeration of rooted 3-connected bipartite planar maps
• Asymptotic properties of random unlabelled block-weighted graphs
• Limits of random tree-like discrete structures
• Subcritical Graph Classes Containing All Planar Graphs
• Enumeration of chordal planar graphs and maps
• Title not available (Why is that?)
• Maximal independent sets and maximal matchings in series-parallel and related graph classes
• Encoding and avoiding 2-connected patterns in polygon dissections and outerplanar graphs
• 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)