Subgraph statistics in subcritical graph classes1. Issue 4 (10th April 2017)
- Record Type:
- Journal Article
- Title:
- Subgraph statistics in subcritical graph classes1. Issue 4 (10th April 2017)
- Main Title:
- Subgraph statistics in subcritical graph classes1
- Authors:
- Drmota, Michael
Ramos, Lander
Rué, Juanjo - Abstract:
- Abstract: Let H be a fixed graph and G a subcritical graph class. In this paper we show that the number of occurrences of H (as a subgraph) in a graph in G 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
- Is Part Of:
- Random structures & algorithms. Volume 51:Issue 4(2017)
- Journal:
- Random structures & algorithms
- Issue:
- Volume 51:Issue 4(2017)
- Issue Display:
- Volume 51, Issue 4 (2017)
- Year:
- 2017
- Volume:
- 51
- Issue:
- 4
- Issue Sort Value:
- 2017-0051-0004-0000
- Page Start:
- 631
- Page End:
- 673
- Publication Date:
- 2017-04-10
- Subjects:
- analytic combinatorics -- generating functions -- random graphs -- subcritical graph classes -- series‐parallel graphs
Random graphs -- Periodicals
Mathematical analysis -- Periodicals
519 - Journal URLs:
- http://onlinelibrary.wiley.com/journal/10.1002/(ISSN)1098-2418 ↗
http://onlinelibrary.wiley.com/ ↗ - DOI:
- 10.1002/rsa.20721 ↗
- Languages:
- English
- ISSNs:
- 1042-9832
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 7254.411950
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 4741.xml