The generalized 3-connectivity of some Regular Networks

For a vertex set S with cardinality at least two, we need a tree to connect them, where this tree is usually called an S-Steiner tree (or a tree connecting S). Two S-Steiner trees T and T' are said to be internally disjoint if E(T) boolean AND E(T') = empty set and V(T) boolean AND V(T') = S. Let K-G(S) denote the maximum number r of internally disjoint S-Steiner trees in G. For an integer k with 2 < k < n, the generalized k-connectivity of a graph G is defined as K-k(G) = min[K-G(S)I IS subset of V(G) and vertical bar S vertical bar = k}. It is proved NP-complete to determine K-k(G) for a general graph G. So far, the exact values of K-k(G) are known for small classes of graphs and most of them are about k = 3. In this paper, we introduce a family of m-regular and m-connected graph G(n) which are constructed recursively and contains many important interconnection networks such as the alternating group graph AG(n) the k-ary n-cube (2,;', the split-star network S-n(2) and the bubble-sort-star graph BSn. We study the generalized 3-connectivity of G(n) and show that k(3)(Gn) = m - 1, which attains the upper bound of K3(G) given by Li et al. for G = G(n). As applications, the generalized 3-connectivity of AG(n) 5,2 and Bs(n), etc., can be obtained directly. (C) 2019 Elsevier Inc. All rights reserved.