The Degree Sequence of Random Graphs from Subcritical Classes
Authors:
- 1 September 2009
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 18 (5) , 647-681
Abstract
In this work we determine the expected number of vertices of degreek=k(n) in a graph withnvertices that is drawn uniformly at random from asubcritical graph class. Examples of such classes are outerplanar, series-parallel, cactus and clique graphs. Moreover, we provide exponentially small bounds for the probability that the quantities in question deviate from their expected values.Keywords
This publication has 13 references indexed in Scilit:
- Analytic Combinatorics2009
- A Complete Grammar for Decomposing a Family of Graphs into 3-Connected ComponentsThe Electronic Journal of Combinatorics, 2008
- Random planar graphsJournal of Combinatorial Theory, Series B, 2005
- Boltzmann Samplers for the Random Generation of Combinatorial StructuresCombinatorics, Probability and Computing, 2004
- Random Graphs2001
- Random Graphs2000
- Enumerative Combinatorics1997
- A calculus for the random generation of labelled combinatorial structuresTheoretical Computer Science, 1994
- Counting labelled three-connected and homeomorphically irreducible two-connected graphsJournal of Combinatorial Theory, Series B, 1982
- On the maximum degree in a random tree.The Michigan Mathematical Journal, 1968