On the maximal connected component of hypercube with faulty vertices
Xiaofan Yang, David John Evans, Bill Chen, Graham M. Megson, Hong‐Jian Lai · International Journal of Computer Mathematics · 2004
In evaluating an interconnection network, it is indispensable to estimate the size of the maximal connected components of the underlying graph when the network begins to lose processors. Hypercube is one of the most popular interconnection networks. This article addresses the maximal connected components of an n-dimensional cube with faulty processors. We first prove that an n-cube with a set F of at most 2n − 3 failing processors has a component of size ≥2 n − |F| − 1. We then prove that an n-cube with a set F of at most 3n − 6 missing processors has a component of size ≥2 n − |F| − 2.