Combinatorial analysis of the fault-diameter of the n-cube

Citation data:

IEEE Transactions on Computers, ISSN: 0018-9340, Vol: 42, Issue: 1, Page: 27-33

Publication Year:
Usage 24
Abstract Views 24
Citations 61
Citation Indexes 61
Repository URL:;
Latifi, Shahram
Institute of Electrical and Electronics Engineers (IEEE)
Computer Science; Mathematics; Engineering; Computer network resources; Fault-tolerant computing; Hypercube networks (Computer networks); Routing (Computer network management); Computer and Systems Architecture; Computer Engineering; Digital Circuits; Digital Communications and Networking; Electrical and Computer Engineering; Systems and Communications
article description
We present a simple method to show that the diameter of an n-dimensional hypercube can only increase by an additive constant of 1 when (n — 1) faulty processors are present. Based on the concept of Forbidden Faulty Sets [1], which guarantees the connectivity of the cube in the presence of up to (2 n - 3) faulty processors, we show that the diameter of the n-cube increases to (n + 2) as a result of (2n — 3) processor failures. More interestingly, we show that only those nodes whose Hamming distance is (n - 2) have the potential to be located at two ends of the diameter of the damaged cube. It is further proven that all the n-cubes with (2n — 3) faulty processors and a fault-diameter of (n + 2) are isomorphic. Finally, a generalization to the subject study is presented. © 1993 IEEE