The block connectivity of random trees (Q1010911)

Summary: Let \(r,m\), and \(n\) be positive integers such that \(rm=n\). For each \(i \in \{1, \dots, m\}\) let \(B_i = \{r(i-1)+1, \dots, 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.