The Generalized Connectivity of Complete Equipartition 3-Partite Graphs

Let G be a nontrivial connected graph of order n, and k an integer with 2 ? k ? n. For a set S of k vertices of G, let ?(S) denote the maximum number ` of edge-disjoint trees T1,T2,...,T` in G such that V(Ti) ?V(Tj) = S for every pair of distinct integers i, j with 1 ? i, j ? `. Chartrand et al. generalized the concept of connectivity as follows: The kconnectivity of G, denoted by ?k(G), is defined by ?k(G) =min{?(S)}, where the minimum is taken over all k-subsets S of V(G). Thus ?2(G) = ?(G), where ?(G) is the connectivity of G; whereas, ?n(G) is the maximum number of edge-disjoint spanning trees contained in G. This paper mainly focuses on the k-connectivity of complete equipartition 3-partite graphs K 3 b , where b ? 2 is an integer. First, we obtain the number of edge-disjoint spanning trees of a general complete 3-partite graph Kx,y,z , which is b(xy+yz+zx)/(x+y+z?1)c. Then, based on this result, we get the k-connectivity of K 3 b for all 3 ? k ? 3b. Namely, ?k(K 3 b ) = ? ??????? ??????? j d k 2 3 e+k 2?2kb 2(k?1) k +3b?k if k ? 3b 2 ; ¥ 3b 2 ¦ if k < 3b 2 and k = 0 (mod 3); ¥ 3bk+3b?k+1 2k+1 ¦ if 3b 4 < k < 3b 2 and k = 1 (mod 3); ¥ 3bk+6b?2k+1 2k+2 ¦ if b ? k < 3b 2 and k = 2 (mod 3); ¥ 3b+1 2 ¦ otherwise. 2010 Mathematics Subject Classification: 05C40, 05C05