McGrae, Andrew R. A.; Zito, Michele The block connectivity of random trees. (English) Zbl 1178.05086 Electron. J. Comb. 16, No. 1, Research Paper R8, 12 p. (2009). 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. MSC: 05C80 Random graphs (graph-theoretic aspects) 05C05 Trees 05C40 Connectivity Keywords:r-block connectivity; vertex connectivity; collapsing vertices; random tree PDFBibTeX XMLCite \textit{A. R. A. McGrae} and \textit{M. Zito}, Electron. J. Comb. 16, No. 1, Research Paper R8, 12 p. (2009; Zbl 1178.05086) Full Text: EuDML EMIS