FAITHFUL 1-EDGE FAULT-TOLERANT GRAPHS

A graph G is 1-edge fault tolerant with respect to a graph G, denoted by 1-EFT(G), if any graph obtained by removing an edge from G contai ns G. A 1-EFT(G) graph is said to be optimal if it contains the minimu m number of edges among all 1-EFT(G) graphs. Let G(i) be 1-EFT(G(i)) for i = 1,2. It can be easily verified that the cartesian product grap h G(1) x G(2)* is 1-edge fault tolerant with respect to the cartesian product graph G(1) x G(2). However, G(1) x G(2)* may contain too man y edges; hence it may nor be optimal for many cases. In this paper, we introduce the concept of faithful graph with respect to a given graph , which is proved to be 1-edge fault tolerant. Based on this concept, we present a construction method of the 1-EFT graph for the cartesian product of several graphs. Applying this construction scheme, we can o btain optimal 1-edge fault tolerant graphs with respect to n-dimension al tori C(m(1), m(2),...,m(n)), where m(i) greater than or equal to 4 are even integers for all 1 less than or equal to i less than or equal to n. (C) 1997 Elsevier Science B.V.