Asymptotic study of subcritical graph classes

Details Asymptotic study of subcritical graph classes Asymptotic study of subcritical graph classes

2010-03-24

arxiv.org/abs/1003.4699v1

Mathematics

Combinatorics

38 pages, 1 figure, 4 tables

Scientific paper

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 both in 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 ${\cG}=\cup_n {\cG_n}$ satisfies asymptotically the universal behaviour $$ g_n = c n^{-5/2} \gamma^n (1+o(1)) $$ for computable constants $c,\gamma$, e.g. $\gamma\approx 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 $\cG_n$, converges (after rescaling) to a normal law as $n\to\infty$.

Affiliated with

Also associated with

No associations

Rating

Asymptotic study of subcritical graph classes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Asymptotic study of subcritical graph classes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymptotic study of subcritical graph classes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-57507