Abstract: We consider the problem of determining the minimum number of faulty processors, k(n,m), and of faulty links, l(n,m), in an n-dimensional hypercube computer so that every m-dimensional subcube is faulty. Equivalently, we determine the minimum number of vertices or edges that must be removed from a hypercube graph so that there is no remaining subgraph of the desired form. For example, in the 3-dimensional cube, removing just 2 vertices at opposite corners of the cube results in no 2-dimensional subcube remaining. However, to destroy every 2-cube by removing edges requires at least 3 edges (proof left to the reader). For a 4-dimensional hypercube, to destroy every 2-cube requires removing at least 5 vertices or at least 8 edges. We do not examine the scenario where both edges and vertices may be removed.

Best known lower bounds for k(n,m) and l(n,m) are proven, several new recursive inequalities and new upper bounds are established, their asymptotic behavior for fixed m and for fixed n-m are analyzed, and their exact values are determined for small n and m. A wide range of techniques and results are presented because no single result is optimal all values of n and m.

Most of the methods employed are constructive, explicitly showing how to select a set of faults attaining the bound. An extensive survey of related work is also included, showing connections to resource allocation in hypercube computers, k-independent sets, and exhaustive testing. Several open questions are also mentioned.

Keywords: hypercube computer, n-cube graph, fault-tolerance, Turan problem, k-independent sets, binary covering array, partitions, resource allocation

Complete paper. This appears in Information and Computation 102 (1993), pp. 280-314. Most of the work had appeared far earlier in a 1987 U. Michigan technical report.

Copyright © 2006-2024 Quentin F. Stout