Back to Search
Start Over
Subgraph statistics in subcritical graph classes
- Source :
- UPCommons. Portal del coneixement obert de la UPC, Universitat Politècnica de Catalunya (UPC), Recercat. Dipósit de la Recerca de Catalunya, instname
- Publication Year :
- 2017
- Publisher :
- Wiley, 2017.
-
Abstract
- Let $H$ be a fixed graph and $\mathcal{G}$ 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 $\mathcal{G}$ 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.<br />Comment: 32 pages, 6 figures
- Subjects :
- Class (set theory)
Combinatorial analysis
General Mathematics
Infinite systems
Asymptotic distribution
series-parallel graphs
0102 computer and information sciences
01 natural sciences
Combinatorics
generating functions
analytic combinatorics
FOS: Mathematics
Mathematics - Combinatorics
Order (group theory)
0101 mathematics
random graphs
Mathematics
Random graph
Applied Mathematics
Probability (math.PR)
010102 general mathematics
Matemàtiques i estadística [Àrees temàtiques de la UPC]
Computer Graphics and Computer-Aided Design
Graph
010201 computation theory & mathematics
Analytic combinatorics
struct
Combinatorics (math.CO)
subcritical graph classes
Mathematics - Probability
Software
Anàlisi combinatòria
Subjects
Details
- ISSN :
- 10429832
- Volume :
- 51
- Database :
- OpenAIRE
- Journal :
- Random Structures & Algorithms
- Accession number :
- edsair.doi.dedup.....f6a65a2bc153fad97946ee4ae4ea6383