The generalized 3-connectivity of the folded hypercube $F{Q}_n$

Abstract

The generalized $k$-connectivity of a graph $G$, denoted by ${\kappa }_k(G)$, is a generalization of the traditional connectivity. 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 $F{Q}_n$ is 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(F{Q}_n)=n$ for $n\ge 2$, that is, for any three vertices in $F{Q}_n$, there exist $n$ internally disjoint trees connecting them.