The Generalized 3-Connectivity of a Family of Regular Networks

The generalized kk-connectivity of a graph GG, denoted by kappa(k)(G), is the minimum number of internally edge disjoint SS-trees for any S subset of V(G) with |S|=k. The generalized kk-connectivity of a graph is a natural extension of the classical connectivity and can be served as an essential parameter for measuring reliability and fault tolerance of the network. Hierarchical interconnection networks (HIN's) are very important in applications related to the modern interconnection networks since they posses many desirable properties. In this paper, we firstly introduce a family of regular networks HG(n) that can be obtained from G(n)(1)boolean OR G(n)(2)boolean OR center dot center dot center dot boolean OR G(n)(t) by adding a matching, where G(n)(i) and G(n)(j) are vertex-disjoint subgraphs and each G(n)(i) is isomorphic to a given graph G(n) (1 <= i<j <= t). Then we determine the generalized 3-connectivity of HG(n). As applications of the main result, the generalized 3-connectivity of some HIN's, such as the hierarchical star network HSn, the hierarchical cubic network HCNn and the hierarchical folded hypercube HFQ(n), can be determined immediately.