Abstract
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]
Acknowledgement
This research was supported by the Visiting Scholar's Funds of the National Education Ministry and the Key Laboratory of Electro-Optical Techniques and Systems, Chongqing University.
Notes
E-mail: [email protected]