The Generalized 3-Connectivity Of The Folded Hypercube FQn

Abstract The generalized $k$-connectivity of a graph $G$, denoted by $\kappa _k(G)$, is a generalization of the traditional connectivity and can serve for measuring the capability of a network $G$ to connect any $k$ vertices in $G$. It is well known that the generalized $k$-connectivity is an important indicator for measuring the fault tolerance and reliability of interconnection networks. The $n$-dimensional folded hypercube $FQ_n$, which is an important variation of hypercubes, can be obtained from the $n$-dimensional hypercube $Q_n$ by adding an edge between any pair of vertices with complementary addresses. In this paper, we show that $\kappa _3(FQ_n)=n$ for $n\ge 2$, that is, for any three vertices in $FQ_n$, there exist $n$ internally disjoint trees connecting them.