The Generalized 3-Connectivity of a Family of Regular Networks

The generalized [Formula: see text]-connectivity of a graph [Formula: see text], denoted by [Formula: see text], is the minimum number of internally edge disjoint [Formula: see text]-trees for any [Formula: see text] with [Formula: see text]. The generalized [Formula: see text]-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 [Formula: see text] that can be obtained from [Formula: see text] by adding a matching, where [Formula: see text] and [Formula: see text] are vertex-disjoint subgraphs and each [Formula: see text] is isomorphic to a given graph [Formula: see text] ([Formula: see text]). Then we determine the generalized 3-connectivity of [Formula: see text]. As applications of the main result, the generalized 3-connectivity of some HIN’s, such as the hierarchical star network [Formula: see text], the hierarchical cubic network [Formula: see text] and the hierarchical folded hypercube [Formula: see text], can be determined immediately.