Fault-tolerant graphs for hypercubes and tori

Motivated by the design of fault-tolerant multiprocessor interconnection networks, this paper considers the following problem: Given a positive integer t and a graph H, construct a graph G from H by adding a minimum number Delta(t, H) of edges such that even after deleting any t edges from G the remaining graph contains H as a subgraph. We estimate Delta(t, H) for the hypercube and torus, which are well-known as important interconnection networks for multiprocessor systems. If we denote the hypercube and the square torus on N vertices by Q(N) and D-N respectively, we show, among others, that Delta(t, Q(N)) = O (tN log(log N/t + log 2e)) for any t and N (t greater than or equal to 2), and Delta, (1, D-N) = N/2 for N even.