Enumeration of Unlabeled Outerplanar Graphs

Details Enumeration of Unlabeled Outerplanar Graphs Enumeration of Unlabeled Outerplanar Graphs

2005-11-16

arxiv.org/abs/math/0511422v2

Mathematics

Combinatorics

25 pages, 5 figures

Scientific paper

We determine the exact and asymptotic number of unlabeled outerplanar graphs. The exact number g_n of unlabeled outerplanar graphs on n vertices can be computed in polynomial time, and g_n is asymptotically $g n^{-5/2}\rho^{-n}$, where $g\approx0.00909941$ and $\rho^{-1}\approx7.50360$ can be approximated. Using our enumerative results we investigate several statistical properties of random unlabeled outerplanar graphs on n vertices, for instance concerning connectedness, chromatic number, and the number of edges. To obtain the results we combine classical cycle index enumeration with recent results from analytic combinatorics.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-588240