1-EDGE FAULT-TOLERANT DESIGNS FOR MESHES
Ray-Shyng Chou, Lih‐Hsing Hsu · Parallel Processing Letters · 1994
A graph G* is k-edge fault-tolerant with respect to a graph G, denoted by k- EFT (G), if every graph obtained by removing any k edges from G* contains G. A k- EFT (G) graph is optimal if it contains the minimum number of edges among all k- EFT (G) graphs. Recently, Harary and Hayes have presented a design which is 1-EFT with respect to meshes and conjectured that their design is optimal. We prove their conjecture is false by giving another design which is 1-EFT with respect to meshes.