Edge fault tolerance in graphs
Frank Harary, John P. Hayes · Networks · 1993
Abstract A graph or multigraph G* is k‐edge fault‐tolerant with respect to a graph G, denoted k‐EFT(G), if every graph obtained by removing any k edges from G* contains G. We observe that for k sufficiently large a k‐EFT(G) graph must be a multigraph, and we present some basic conditions that such multigraphs must meet. We then study the problem of constructing k‐EFT(G) graphs that are optimal in that they contain the minimum number of edges among all k‐EFT(G) graphs. Families of optimal k‐EFT(G) graphs, where G is the n‐node path or cycle, are presented for all k and n. We also give an optimal 1‐EFT design for the n‐dimensional hypercube. © 1993 by John Wiley & Sons, Inc.