Routing properties of supercubes

Abstract

Usually each vertex of the (s + 1)-dimensional hypercube is labeled with a unique integer k with 0 less than or equal to k less than or equal to 2(s+1) - 1. The supercube S-N of N nodes with 2(s) < N <less than or equal to> 2(s+1) is constructed by merging nodes u and u - 2(s), with N less than or equal to u less than or equal to 2(s+1) - 1, in the (s + 1)-dimensional hypercube into a single node labeled as u - 2(s) and leaving other nodes in the (s + I)-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 S-N Then we show how to construct kappa (S-N) disjoint paths between any two nodes of the supercube, where kappa (S-N) is the connectivity of S-N. 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 is an element of (2(s+1) - 2(i) + 1 0 less than or equal to i less than or equal to s - 1) and s + 1 otherwise. (C) 2001 Elsevier Science Inc. All rights reserved.