The Generalized 3-Connectivity of Cayley Graphs on Symmetric Groups Generated by Trees and Cycles

The generalized connectivity of a graph is a natural generalization of the connectivity and can serve for measuring the capability of a network G to connect any k vertices in G. Given a graph and a subset of at least two vertices, we denote by the maximum number r of edge-disjoint trees in G such that for any pair of distinct integers i, j, where . For an integer k with , the generalized k-connectivity is defined as . That is, is the minimum value of over all k-subsets S of vertices. The study of Cayley graphs has many applications in the field of design and analysis of interconnection networks. Let Sym(n) be the group of all permutations on and be a set of transpositions of Sym(n). Let be the graph on n vertices such that there is an edge ij in if and only if the transposition . If is a tree, we use the notation to denote the Cayley graph on symmetric groups generated by . If is a cycle, we use the notation to denote the Cayley graph on symmetric groups generated by . In this paper, we investigate the generalized 3-connectivity of T-n and MBn and show that kappa(3) (T-n) = n - 2 and kappa(3) (MBn) = n - 2.