The generalized 3-connectivity of a family regular networks

Abstract

The generalized $k$-connectivity of a graph $G$, denoted by ${\kappa }_k(G)$, is the minimum number of internally edge disjoint $S$-trees for any $S\subseteq V(G)$ with $|S|=k$. The generalized $k$-connectivity is a natural extension of the classical connectivity and plays a key role in applications related to the modern interconnection networks. In this paper, we firstly introduce a family of regular networks $H_n$ that can be obtained from several subgraphs $G_n^1,G_n^2,\cdots ,G_n^{t_n}$ by adding a matching, where each subgraph $G_n^i$ is isomorphic to a particular graph $G_n$ ($1\le i\le t_n$). Then we determine the generalized 3-connectivity of $H_n$. As applications of the main result, the generalized 3-connectivity of some two-level interconnection networks, such as the hierarchical star graph $H{S}_n$, the hierarchical cubic network $HC{N}_n$ and the hierarchical folded hypercube $HF{Q}_n$, are determined directly.