The block connectivity of random trees

Andrew R. A. McGrae ; Michele Zito

The electronic journal of combinatorics, Tome 16 (2009) no. 1

Résumé

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

Détail

DOI : 10.37236/97

Classification : 05C80, 05C05, 05C40
Mots-clés : r-block connectivity, vertex connectivity, collapsing vertices, random tree