Fault-Tolerant Graphs for Hypercubes and Tori *
Toshinori Yamada, Koji Yamamoto, Shuichi Ueno · 1996
Motivated by the design of fault-tolerant multipro-cessor interconnection networks, this paper considers the following problem: Given a positive integer t and graph H, construct a graph G from H by adding a min-imum number A(t, H) of edges such that even after deleting any t edges from G the remaining graph con-tains H as a subgraph. We estimate A(t, H) for the hypercube and torus, which are well-known as impor-tant interconnection networks for multiprocessor sys-tems. If we denote the hypercube and square torus on N vertices by QN and DN, respectively, we show, among others, that A(t, QN) = C(tNlog(v + log2e)) for any t and N (t 2 2), and A(l, DN) = $ if N is even.