The block connectivity of random trees
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.
- The connectivity-profile of random increasing \(k\)-trees
- Random Trees in Random Graphs
- Trees in random graphs
- scientific article; zbMATH DE number 1380601
- scientific article; zbMATH DE number 6123974
- Trees in sparse random graphs
- Connectivity of random geometric graphs related to minimal spanning forests
- scientific article; zbMATH DE number 747032
- Spanning trees in random graphs
- On the tree-depth of random graphs
This page was built for publication: The block connectivity of random trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010911)
