Super-Connectivity of the Folded Locally Twisted Cube

Abstract

The hypercube Qn is one of the most popular interconnection networks with high symmetry. To reduce the diameter of Qn, many variants of Qn have been proposed, such as the n-dimensional locally twisted cube LTQn. To further optimize the diameter of LTQn, the n-dimensional folded locally twisted cube FLTQn is proposed, which is built based on LTQn by adding 2n−1 complementary edges. Connectivity is an important indicator to measure the fault tolerance and reliability of a network. However, the connectivity has an obvious shortcoming, in that it assumes all the adjacent vertices of a vertex will fail at the same time. Super-connectivity is a more refined index to judge the fault tolerance of a network, which ensures that each vertex has at least one neighbor. In this paper, we show that the super-connectivity κ(1)(FLTQn)=2n for any integer n≥6, which is about twice κ(FLTQn).

Keywords

• super-connectivity
• folded locally twisted cube
• fault tolerance
• interconnection network
• reliability