On the maximal connected component of hypercube with faulty vertices (II)

Yang, X. F., Evans, D. J. and Megson, G. M. (2004) On the maximal connected component of hypercube with faulty vertices (II). International Journal of Computer Mathematics, 81 (10). pp. 1175-1185. ISSN 0020-7160 doi: 10.1080/0020716041233127208

Abstract/Summary

evaluating the fault tolerance of an interconnection network, it is essential to estimate the size of a maximal connected component of the network at the presence of faulty processors. Hypercube is one of the most popular interconnection networks. In this paper, we prove that for ngreater than or equal to6, an n-dimensional cube with a set F of at most (4n-10) failing processors has a component of size greater than or equal to2"-\F-3. This result demonstrates the superiority of hypercube in terms of the fault tolerance.