,
On the number of series parallel and outerplanar graphs
(апреля 2008)
Аннотация
Abstract. We show that the number gn of labelled
series-parallel graphs on n vertices is asymptotically gn
∼ g · n −5/2 γ n n!, where γ and g are explicit
computable constants. We show that the number of edges in
random seriesparallel 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. A graph
is series-parallel (SP for short) if it does not contain the
complete graph K4 as a minor; equivalently, if it does not
contain a subdivision of K4. Since both K5 and K3,3 contain
a subdivision of K4, by Kuratowski’s theorem a SP graph is
planar. Another characterization, justifying the name, is
the following. A connected graph is SP if it can be obtained
from a single edge by means of the the following two
operations: subdividing an edge (series); and duplicating an
edge (parallel). In addition, a 2-connected graph is SP if
it can be obtained from a double edge by means of series and
parallel operations; in particular, this implies that a
simple 2-connected SP graph has always a vertex of degree
two. Although SP operations
