Journal
SIAM JOURNAL ON DISCRETE MATHEMATICS
Volume 25, Issue 4, Pages 1615-1651Publisher
SIAM PUBLICATIONS
DOI: 10.1137/100790161
Keywords
random graph; asymptotic enumeration; limit law; analytic combinatorics
Categories
Funding
- Austrian Science Foundation FWF [9604]
- European Research Council under the European Community [208471]
Ask authors/readers for more resources
We present a unified general method for the asymptotic study of graphs from the so-called subcritical graph classes, which include the classes of cacti graphs, outerplanar graphs, and series-parallel graphs. This general method works in both the labelled and unlabelled framework. The main results concern the asymptotic enumeration and the limit laws of properties of random graphs chosen from subcritical classes. We show that the number g(n)/n! (resp., g(n)) of labelled (resp., unlabelled) graphs on n vertices from a subcritical graph class g = boolean OR(n)g(n) satisfies asymptotically the universal behavior g(n) = c n(-5/2) gamma(n) (1 + o(1)) for computable constants c, gamma, e.g., gamma approximate to 9.38527 for unlabelled series-parallel graphs, and that the number of vertices of degree k (k fixed) in a graph chosen uniformly at random from g(n) converges (after rescaling) to a normal law as n -> infinity.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available