The Block Connectivity of Random Trees

Abstract

Let $r$, $m$, and $n$ be positive integers such that $rm=n$. For each $i \in \{1, \ldots, m\}$ let $B_i = \{r(i-1)+1, \ldots, ri\}$. The $r$-block connectivity of a tree on $n$ labelled vertices is the vertex connectivity of the graph obtained by collapsing the vertices in $B_i$, for each $i,$ to a single (pseudo-)vertex $v_i$. In this paper we prove that, for fixed values of $r$, with $r \geq 2$, the $r$-block connectivity of a random tree on $n$ vertices, for large values of $n$, is likely to be either $r-1$ or $r$, and furthermore that $r-1$ is the right answer for a constant fraction of all trees on $n$ vertices.