On Minimum Fault-Tolerant Networks
S. Ueno, Amitabha Bagchi, S. L. Hakimi, Edward F. Schmeichel · SIAM Journal on Discrete Mathematics · 1993
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 $\Delta ( t,H )$ (respectively, $\Delta ' ( t,H )$) of edges and an appropriate number of vertices, such that after removing any t vertices (respectively, t edges) from G the remaining graph contains H as a subgraph. This problem was motivated by the design of fault-tolerant interconnection networks for multiprocessor systems. The authors estimate $\Delta ( t,H )$ and $\Delta ' ( t,H )$ for the cycle, path, complete binary tree, grid, torus, and hypercube on n vertices.