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

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.

Keywords:

• Interconnection network
• Fault tolerance
• Maximal connected component
• Hypercube

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.