hide
Free keywords:
-
Abstract:
Let $\mathcal{C}$ be a class of labeled connected graphs, and let $C_n$ be a
graph drawn uniformly at random from graphs in $\mathcal{C}$ that contain
exactly $n$ vertices. Denote by~$b(\ell;\, C_n)$ the number of blocks (i.e.\
maximal biconnected subgraphs) of~$C_n$ that contain exactly~$\ell$ vertices,
and let~$lb(C_n)$ be the number of vertices in a largest block of~$C_n$. We
show that under certain general assumptions on~$\mathcal{C}$, $C_n$ belongs
with high probability to one of the following categories:
\begin{itemize}
\item[(1)] $lb(C_n) \sim cn$, for some explicitly given $c = c(\mathcal{C})$,
and the second largest block is of order $n^{\alpha}$, where $1 > \alpha =
\alpha(\mathcal{C})$, or
\item[(2)] $lb(C_n) = \mathcal{O}(\log n)$, i.e., all blocks contain at most
logarithmically many vertices.
\end{itemize}
Moreover, in both cases we show that the quantity $b(\ell;\, C_n)$ is
concentrated for all $\ell$, and we determine its expected value. As a
corollary we obtain that the class of planar graphs belongs to category (1). In
contrast to that, outerplanar and series-parallel graphs belong to
category~(2).
