The block connectivity of random trees (Q1010911)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The block connectivity of random trees |
scientific article |
Statements
The block connectivity of random trees (English)
0 references
7 April 2009
0 references
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.
0 references
r-block connectivity
0 references
vertex connectivity
0 references
collapsing vertices
0 references
random tree
0 references