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. This problem is the same as determining 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, one must remove 3 edges to destroy every 2-cube (proof left to the reader). For a 4-dimensional hypercube, one needs to remove at least 5 vertices, or at least 8 edges, to destroy every 2-cube (see Figure 1 in the paper).

Best known lower bounds for k(n,m) and l(n,m) are proved, 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 bound is sufficiently good for all values of n and m.

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

Keywords: hypercube computer, graph theory, n-cube, fault-tolerance, Turan problem, k-independent sets, partitions, resource allocation, discrete mathematics, computer science

Complete paper. This paper appears in Information and Computation 102 (1993), pp. 280-314.

Copyright © 2006-2009 Quentin F. Stout