Routing Properties of Supercubes

Abstract

Usually each vertex of the (s+1)-dimensional hypercube is labeled with a unique integer k with 0⩽k⩽2s+1−1. The supercube SN of N nodes with 2s<N⩽2s+1 is constructed by merging nodes u and u−2s, with N⩽u⩽2s+1−1, in the (s+1)-dimensional hypercube into a single node labeled as u−2s and leaving other nodes in the (s+1)-dimensional hypercube unchanged. In this paper, we give the exact distance between any two nodes of supercube and present a new shortest path routing algorithm on SN. Then we show how to construct κ(SN) disjoint paths between any two nodes of the supercube, where κ(SN) is the connectivity of SN. Finally, we compute the wide diameter and the fault diameter of SN. We show that both the wide diameter and the fault diameter are equal to s+2 if N∈{2s+1−2i+1∣0⩽i⩽s−1} and s+1 otherwise.