Faithful 1-edge fault tolerant graphs

✍ Scribed by Shih-Yih Wang; Lih-Hsing Hsu; Ting-Yi Sung

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 726 KB
• Volume: 61
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00003-3

✦ Synopsis

A graph G* is l-edge fault tolerant with respect to a graph G, denoted by I-EFT( G), if any graph obtained by removing an edge from G' contains G. A l-Em(G)

graph is said to be optimal if it contains the minimum number of edges among all I-EFT( G) graphs. Let Gf be 1 -EJ!T( Gi) for i = 1,2. It can be easily verified that the Cartesian product graph G; x G; is l-edge fault tolerant with respect to the Cartesian product graph GI x Gz, However, G; x G; may contain too many edges; hence it may not 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 l-edge fault tolerant. Based on this concept, we present a construction method of the I-EIT graph for the Cartesian product of several graphs. Applying this construction scheme, we can obtain optimal l-edge fault tolerant graphs with respect to n-dimensional tori C(ml, m2,. . , m,), where rni 2 4 are even integers for all 1 < i < n. @ 1997 Elsevier Science B.V.