On the maximal connected component of hypercube with faulty vertices (II)
Xiaofan Yang, David John Evans, Graham M. Megson · International Journal of Computer Mathematics · 2004
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.