Abstract
In 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 n ≥ 6, an n-dimensional cube with a set F of at most (4n − 10) failing processors has a component of size ≥2″ − |F| − 3. This result demonstrates the superiority of hypercube in terms of the fault tolerance.
Acknowledgement
This research was partly supported by the Visiting Scholar's Funds of National Education Ministry's Key Laboratory of Electro-Optical Technique and System, Chongqing University.