Previous works on edge-fault tolerance with respect to hypercubes Q/sub n/ are mainly focused on 1-edge fault and 2- or 3-edge fault with limited size of n. We give a construction scheme for 2-EFT(Q/sub n/) graphs and 3-EFT(Q/sub n/) graphs, where n is arbitrarily large. In our constructions, approximately log n extra degree is added to the vertices of Q/sub n/ for 2-edge-fault tolerance, and one more degree for 3-edge-fault tolerance.

Architectures for interconnection networks can be represented by graphs, while vertices represent processors and edges represent communication links between processors. We use the terms vertices and processors interchangeably. Let G = (V, E) be a graph representing the topology for an interconnection network. Let v0 be a special vertex outside G, called the host processor, which is connected to each vertex in G. The host processor is the sender or source of the message to be transmitted to all of the vertices in G. In each time unit, the host processor may send an identical message to an arbitrary vertex in G or remain idle. At the same time, each processor in G that has already received the message can send it to all its neighbors in one time unit. A transmitting scheme allowing all processors to receive the message in t time units and requiring the host processor to send the message s times is called a (t, s)-transmitting scheme, where t ≥ s. We call t the transmitting time, and s, the workload of the host processor. We aimed to find an optimal transmitting scheme, i.e., a transmitting scheme such that t is minimized while s is also minimized. In this paper, we present optimal transmitting schemes for linear arrays, rings, complete binary trees, star trees, and (directed) de Bruijn graphs. Furthermore, we present a (t, s)-transmitting scheme for diagonal meshes which are defined slightly different from meshes, and the ratio of t to the optimal transmitting time is approximate to 1.1. © 1996 John Wiley & Sons, Inc.