Enumeration and Asymptotic Properties of Unlabeled Outerplanar Graphs
By Manuel Bodirsky, Eric Fusy, Mihyun Kang, and Stefan VigerskeElectronic Journal of Combinatorics 14 (2007), #R66, 24 pages
Part of Master's Thesis of Stefan Vigerske (Asymptotic 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 and rho can be approximated, g is approximately
0.00909941, 1/rho is approximately 7.50360.
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.
For example we show that
the asymptotic probability of a random unlabelled outerplanar
graph chosen uniformly at random being connected can be approximated
by c/g approx. 0.845721.
To obtain the results we combine classical cycle index enumeration with
recent results from analytic combinatorics.
Download
- ps - unlouterplanar.ps
- pdf - unlouterplanar.pdf
Deutsch