Fault tolerance of Möbius cubes under two forbidden fault set models
Xiaofan Yang, Graham M. Megson · International Journal of Computer Mathematics · 2004
An n-dimensional Möbius cube, 0MQn or 1MQn , is a variation of n-dimensional cube Qn which possesses many attractive properties such as significantly smaller communication delay and stronger graph-embedding capabilities. In some practical situations, the fault tolerance of a distributed memory multiprocessor system can be measured more precisely by the connectivity of the underlying graph under forbidden fault set models. This article addresses the connectivity of 0MQn /1MQn under two typical forbidden fault set models. We first prove that the connectivity of 0MQn /1MQn is 2n − 2 when the fault set does not contain the neighborhood of any vertex as a subset. We then prove that the connectivity of 0MQn /1MQn is 3n − 5 provided that the neighborhood of any vertex as well as that of any edge cannot fail simultaneously. These results demonstrate that 0MQn /1MQn has the same connectivity as Qn under either of the previous assumptions. E-mail: [email protected]