Enumeration of Unlabeled Outerplanar Graphs

Abstract

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\approx 0.00909941$ and ${\rho }^{-1}\approx 7.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.

25 pages, 5 figures