Optimal 1-edge fault-tolerant designs for ladders. (Q1853116)

A graph \(G^{*}\) is 1-edge fault-tolerant with respect to a graph \(G,\) denoted by 1-EFT(\(G),\) if every graph obtained by removing any edge from \(G^{*}\) contains \(G.\) A 1-EFT(\(G)\) graph is optimal if it contains the minimum number of edges among all 1-EFT(\(G)\) graphs. The \(kth\) ladder graph, \(L_{k},\) is defined to be the cartesian product of the \(P_{k}\) and \(P_{2}\) where \(P_{n}\) is the \(n\)-vertex path graph. In this paper, we present several \(1\)-edge fault-tolerant graphs with respect to ladders. Some of these graphs are proven to be optimal.