Optimally edge fault-tolerant trees

We study the structure of fault-tolerant multiprocessor systems that allow one or more communication links to fail. Spare links are employed to tolerate link failures; no redundant processing units are required. Such a multiprocessor is modeled by a graph G whose nodes and edges correspond to the processing units and the links, respectively. G is a k-edge fault-tolerant design of a basic graph H, denoted k-EFT(H), if every graph obtained by removing any k edges from G embeds H. If G contains the fewest edges among all k-EFT designs of H, then G is said to be optimally k-EFT with respect to H. We introduce the concept of critical edges and graphs and derive some of their properties that are generally useful in designing optimal EFT supergraphs. We investigate the theory of edge fault tolerance for tree-structured networks, in particular, nonhomogeneous trees and stars. For both cases, we obtain optimal k-EFT designs for all k.