Faithful 1-edge fault tolerant graphs

Abstract

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* contains G. A 1-EFT(G) graph is said to be optimal if it contains the minimum 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 graph 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 many 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 obtain optimal 1-edge fault tolerant graphs with respect to n-dimensional 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.