Item

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).