Fault Tolerant Routing in the Supercube

In this paper we study the fault--tolerant properties of the Supercube, a new interconnection network recently introduced by Sen [15]. The Supercube is a generalization of the Hypercube that can be realized for any number of nodes and not only for powers of 2. Moreover, it has the same diameter and connectivity of the Hypercube. We prove that the diameter of the surviving route graph of the N--node Supercube SN , if less than blog 2 Nc nodes or edges fail, is at most 4 for any minimal routing, and exhibit a minimal routing for which the surviving route graph has diameter 2. Then, we show that, when 2 s + 2 s\Gamma1 N ! 2 s+1 and the failures are dlog 2 Ne, the diameter of the surviving route graph is at most 5 for any minimal routing. We also prove that the fault diameter of SN is exactly blog 2 Nc+ 1 when N 62 f2 s+1 \Gamma 1; 2 s+1 \Gamma 2; 2 s + 2 s\Gamma1 + 1g, and blog 2 Nc+ 2 otherwise. Keywords: Supercube, fault tolerance, routing, surviving route graph, broadc..