Abstract
Motivated by the design of fault-tolerant multiprocessor interconnection networks the paper considers the following problem: given a positive integer t and graph H, construct a graph G from H by adding a minimum number /spl 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 /spl 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 square torus on N vertices by Q/sub N/ and D/sub N/, respectively, we show among others, that /spl Delta/(t,Q/sub N/)=O(tNlog(logN/t+log2e)) for any t and N (t/spl ges/2), and /spl Delta/(1,D/sub N/)=N/2 if N is even.