The generalized connectivity of complete bipartite graphs
Shasha Li, Wei Li, Xueliang Li · Ars Combinatoria · 2010
Let G be a nontrivial connected graph of order n, and k an integer with 2 � kn. For a set S of k vertices of G, let �(S) denote the maximum numberof edge-disjoint trees T1;T2;:::;Tin G such that V (Ti) V (Tj) = S for every pair i;j of distinct integers with 1 � i;j� `. Chartrand et al. generalized the concept of connectivity as follows: The k-c潮nectivity , denoted byk(G), of G is defined byk(G) =minf�(S)g, where the minimum is taken over all k-subsets S of V (G). Thus �2(G) = �(G), where �(G) is the connectivity of G. Moreover, �n(G) is the maximum number of edge-disjoint spanning trees of G. This paper mainly focus on the k-connectivity of complete bipartite graphs Ka;b. First, we obtain the number of edge-disjoint spanning trees of Ka;b, which is b ab a+b−1 c, and specifically give the b ab a+b−1 c edge-disjoint spanning trees. Then based on this result, we get the k-connectivity of Ka;bfor all 2 � ka+b. Namely, if k > b−a+2