The locally twisted cubes

Abstract

This paper introduces a new variant of the popular n-dimensional hypercube network Q _n , known as the n-dimensional locally twisted cube LTQ _n , which has the same number of nodes and the same number of connections per node as Q _n . Furthermore, LTQ _n is similar to Q _n in the sense that the nodes can be one-to-one labeled with 0–1 binary sequences of length n, so that the labels of any two adjacent nodes differ in at most two successive bits. One advantage of LTQ _n is that the diameter is only about half of the diameter of Q _n . We develop a simple routing algorithm for LTQ _n , which creates a shortest path from the source to the destination in O(n) time. We find that LTQ _n consists of two disjoint copies of Q _{n −1} by adding a matching between their nodes. On this basis, we show that LTQ _n has a connectivity of n.

Keywords:

• Interconnection network
• Locally twisted cube
• Routing algorithm
• Diameter
• Connectivity

Acknowledgement

This research was partly supported by the Visiting Scholar’s Funds of National Education Ministry’s Key Laboratory of Electro-Optical Technique and System, Chongqing University.