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
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references