ON MINIMUM FAULT-TOLERANT NETWORKS

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.