Fault-tolerant graphs for tori
Toshinori Yamada, Shuichi Ueno · Networks · 1998
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 Δ(t, H) of edges such that even after deleting any t edges from G the remaining graph contains H as a subgraph. We estimate Δ(t, H) for the torus, which is well known as a very important interconnection network for multiprocessor systems. © 1998 John Wiley & Sons, Inc. Networks 32: 181–188, 1998