Unchanging the diameter of k-ary n-cube networks with faulty vertices

Abstract

The k-ary n-cube is one of the most commonly used interconnection networks for parallel and distributed systems. In this paper, for a k-ary n-cube , we show that if k is even and if k is odd, where is the maximum integer such that the diameter of remains unchanged when arbitrary vertices are faulty. Furthermore, we show that for even k, if the diameter of a faulty with 2n−1 faulty vertices is larger than its fault-free diameter, then all the faulty vertices are adjacent to a certain vertex and there is only one pair of vertices in this such that their distance is equal to the fault diameter. For k-ary n-cubes with odd k, similar results are given.

Keywords:

• interconnection networks
• fault-tolerance
• k-ary n-cube networks
• diameter
• fault diameter

2010 AMS Subject Classifications::

• 05C12
• 94C15
• 68M15

Acknowledgement

This work is supported in part by the National Natural Science Foundation of China (61370001,61303020,U1304601), the Doctoral Fund of Ministry of Education of China (20111401110005) and the Natural Science Foundation of Shanxi Province (2013021018-3).