Abstract
We obtain the conditional fault diameter of the k-ary n-cube interconnection network. It has been previously shown that under the condition of forbidden faulty sets (i.e. assuming each non-faulty node has at least one non-faulty neighbor), the k-ary n-cube, whose connectivity is 2n, can tolerate up to 4n-3 faulty nodes without becoming disconnected. We extend this result by showing that the conditional fault-diameter of the k-ary n-cube is equal to the fault-free diameter plus two. This means that if there are at most 4n-3 faulty nodes in the k-ary n-cube and if every non-faulty node has at least one non-faulty neighbor, then there exists a fault-free path of length at most the diameter plus two between any two non faulty nodes. We also show how to construct these fault-free paths. With this result the k-ary n-cube joins a group of interconnection networks (including the hypercube and the star-graph) whose conditional fault diameter has been shown to be only two units over the fault-free diameter.
Keywords
Publication details
- DOI
- 10.24200/squjs.vol10iss0pp63-75
- Journal
- Sultan Qaboos University Journal for Science, 10, 63
- Publisher
- Sultan Qaboos University
- Open access
- Gold open access
- License
- CC BY 4.0
Cite this article
APA 7
Day, K., & Touzene, A. (2005). The Conditional Fault-Diameter of the K-ary n-Cube. Sultan Qaboos University Journal for Science, 10, 63. https://doi.org/10.24200/squjs.vol10iss0pp63-75
MLA 9
Day, Khaled, and Abderezak Touzene. "The Conditional Fault-Diameter of the K-ary n-Cube." Sultan Qaboos University Journal for Science, vol. 10, 2005, pp. 63. https://doi.org/10.24200/squjs.vol10iss0pp63-75.
Chicago (author–date)
Day, Khaled, and Abderezak Touzene. 2005. "The Conditional Fault-Diameter of the K-ary n-Cube." Sultan Qaboos University Journal for Science 10: 63. https://doi.org/10.24200/squjs.vol10iss0pp63-75.
Harvard
Day, K. and Touzene, A. (2005) 'The Conditional Fault-Diameter of the K-ary n-Cube', Sultan Qaboos University Journal for Science, 10, pp. 63. doi:10.24200/squjs.vol10iss0pp63-75.
Vancouver
Day K, Touzene A. The Conditional Fault-Diameter of the K-ary n-Cube. Sultan Qaboos University Journal for Science. 2005;10:63. doi:10.24200/squjs.vol10iss0pp63-75
IEEE
K. Day, and A. Touzene, "The Conditional Fault-Diameter of the K-ary n-Cube," Sultan Qaboos University Journal for Science, vol. 10, pp. 63, 2005, doi: 10.24200/squjs.vol10iss0pp63-75.