This paper considers the following problem: Given a positive integer t
and graph H, construct a graph G from H by adding a minimum number DE
LTA(t, H) (respectively, DELTA'(t, H)) of edges and an appropriate num
ber of vertices, such that after removing any t vertices (respectively
, t edges) from G the remaining graph contains H as a subgraph. This p
roblem was motivated by the design of fault-tolerant interconnection n
etworks for multiprocessor systems. The authors estimate DELTA(t, H) a
nd DELTA'(t, H) for the cycle, path, complete binary tree, grid, torus
, and hypercube on n vertices.