The Tree Connectivity of Regular Complete Bipartite Graphs

Abstract

For a set $S$ of two or more vertices in a nontrivial connected graph $G$ of order $n$, a collection $\{T_1,T_2,\dots ,T_{\ell }\}$ of trees in $G$ is said to be an internally disjoint set of trees connecting $S$ if these trees are pairwise edge-disjoint and $V(T_i)\cap V(T_j)=S$ for every pair $i,j$ of distinct integers with $1\le i,j\le \ell$. For an integer $k$ with $2\le k\le n$, the tree $k$-connectivity ${\kappa }_k(G)$ of $G$ is the greatest positive integer $\ell$ for which $G$ contains at least $\ell$ internally disjoint trees connecting $S$ for every set $S$ of $k$ vertices of $G$. It is shown for every two integers $k$ and $r$ with $3\le k\le 2r$ that
$${\kappa }_k(K_{r,r})=r–\lceil \frac{k-1}{4}\rceil .$$