Title: Faithful 1-edge fault tolerant graphs
Authors: Wang, SY
Hsu, LH
Sung, TY
Department of Computer Science
Keywords: Cartesian product;Kronecker product;edge fault tolerance;meshes;tori
Issue Date: 28-Feb-1997
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.
URI: http://hdl.handle.net/11536/717
ISSN: 0020-0190
Volume: 61
Issue: 4
Begin Page: 173
End Page: 181
Appears in Collections:Articles

Files in This Item:

  1. A1997WP28400001.pdf