Enumeration and limit laws of series-parallel graphs

Details Enumeration and limit laws of series-parallel graphs Enumeration and limit laws of series-parallel graphs

2005-12-19

arxiv.org/abs/math/0512435v1

Mathematics

Combinatorics

14 pages

Scientific paper

We show that the number $g_n$ of labelled series-parallel graphs on $n$ vertices is asymptotically $g_n \sim g\cdot n^{-5/2} \gamma^n n!$, where $\gamma$ and $g$ are explicit computable constants. We show that the number of edges in random series-parallel graphs is asymptotically normal with linear mean and variance, and that the number of edges is sharply concentrated around its expected value. Similar results are proved for labelled outerplanar graphs and for graphs not containing $K_{2,3}$ as a minor.

Affiliated with

Also associated with

No associations

Rating

Enumeration and limit laws of series-parallel graphs 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 Enumeration and limit laws of series-parallel graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enumeration and limit laws of series-parallel graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-281495