The Generalized Connectivity of Complete Bipartite Graphs

Abstract

Let \(G\) be a nontrivial connected graph of order \(n\), and \(k\) an integer with \(2 \leq k \leq n\). For a set \(S\) of \(k\) vertices of \(G\), let \(\nu(S)\) denote the maximum number \(\ell\) of edge-disjoint trees \(T_1, T_2, \ldots, T_\ell\) in \(G\) such that \(V(T_i) \cap V(T_j) = S\) for every pair \(i, j\) of distinct integers with \(1 \leq i, j \leq \ell\). Chartrand et al. generalized the concept of connectivity as follows: The \(k\)-connectivity, denoted by \(\kappa_k(G)\), of \(G\) is defined by \(\kappa_k(G) = \min\{\nu(S)\}\), where the minimum is taken over all \(k\)-subsets \(S\) of \(V(G)\). Thus \(\kappa_2(G) = \kappa(G)\), where \(\kappa(G)\) is the connectivity of \(G\). Moreover, \(\kappa_n(G)\) is the maximum number of edge-disjoint spanning trees of \(G\).

This paper mainly focuses on the \(k\)-connectivity of complete bipartite graphs \(K_{a,b}\), where \(1 \leq a \leq b\). First, we obtain the number of edge-disjoint spanning trees of \(K_{a,b}\), which is \(\lfloor \frac{ab}{a+b-1}\rfloor \), and specifically give the \(\lfloor \frac{ab}{a+b-1}\rfloor\) edge-disjoint spanning trees. Then, based on this result, we get the \(k\)-connectivity of \(K_{a,b}\) for all \(2 \leq k \leq a + b\). Namely, if \(k > b – a + 2\) and \(a – b + k\) is odd, then \(\kappa_k(K_{a,b}) =\frac{a+b-k+1}{2} \left\lfloor \frac{(a-b + k + 1)(b-a + k – 1)}{4(k-1)} \right\rfloor\), if \(k > b – a + 2\) and \(a – b + k\) is even, then \(\kappa_k(K_{a,b}) = \frac{a+b-k+1}{2} +\left\lceil \frac{(a – b+ k )(a + b – k)}{4(k-1)} \right\rceil\), and if \(k \leq b – a + 2\), then \(\kappa_k(K_{a,b}) = a\).