Asymptotic Enumeration of Unlabelled Outerplanar Graphs
By Stefan VigerskeMaster's Thesis at HU Berlin (Supervised by Dr. Mihyun Kang)
Abstract
Counting labelled planar graphs and labelled or unlabelled planar maps has
been a well-studied problem for many years. The growth rates for labelled
planar, labelled series-parallel, and labelled outerplanar graphs
have been found recently (see
"On the Number of Series Paralle and Outerplanar Graphs").
In this thesis we investigate unlabelled outerplanar graphs.
The analysis of the two-connected components of an unlabelled outerplanar
graph is essential for the construction of generating functions for the
connected and general case. Using singularity analysis, we show that the
number g_n of unlabelled outerplanar graphs on n vertices 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, and that the number of connected
outerplanar graphs on n vertices is asymptotically c n^(-5/2) rho^(-n) where
c is approximately 0.00760471, and rho as before.
Therefore, the asymptotic probability of a random unlabelled outerplanar
graph (sampled uniformly at random) being connected can be approximated
by c/g approx. 0.845721.
Furthermore, we show that the expected number of components in a random
unlabelled outerplanar graph is asymptotically approx. 1.17847 and the
expected number of isolated vertices is asymptotically approx. 0.153761.
Moreover, we approximate the growth rate for bipartite unlabelled outerplanar
graphs and show that the chromatic number of a random unlabelled outerplanar
graph is three with probability tending to one as n goes to infinity.
Finally, we investigate the number of edges in a random unlabelled
outerplanar graph on n vertices and show that their limit distribution is
Gaussian with mean approx. 1.54894n.
