The generalized 3-connectivity of star graphs and bubble-sort graphs

摘要

For S subset of G, let kappa(S) denote the maximum number r of edge-disjoint trees T-1,T-2,TrT1,T-2,,T-r in G such that V(T-i)boolean AND V(T-j)=S for any i,j{1,2,,r} and i not equal j. For every 2 <= k <= n, the generalized k-connectivity of G kappa(k)(G) is defined as the minimum ?(S) over all k-subsets S of vertices, i.e., kappa(k)(G)=min {kappa(S)vertical bar S subset of V(G)and vertical bar S vertical bar=k}. Clearly, kappa(2)(G) corresponds to the traditional connectivity of G. The generalized k-connectivity can serve for measuring the capability of a network G to connect any k vertices in G. Cayley graphs have been used extensively to design interconnection networks. In this paper, we restrict our attention to two classes of Cayley graphs, the star graphs S-n and the bubble-sort graphs B-n, and investigate the generalized 3-connectivity of S-n and B-n . We show that kappa(3)(Sn)=n-2 and kappa(3)(B-n)=n-2. (C) 2015 Elsevier Inc. All rights reserved.