×

Fault tolerance of \(\lambda\)-optimal graphs. (English) Zbl 1474.05226

Summary: A connected graph \(G\) is \(\lambda\)-optimal if \(\lambda(G)=\delta(G)\). A \(\lambda\)-optimal graph is \(t\)-\(\lambda\) optimal connected if for any edge set \(S\subseteq E(G)\) with \(|S|\leq t\), \(G-S\) is still \(\lambda\)-optimal. The maximum integer of such \(t\) denoted by \(O_{\lambda}(G)\) is the edge fault tolerance with respect to \(\lambda\)-optimal edge connectivity. In this paper, we show that \(\min\{\lambda^\prime-\delta,\delta -1\}\leq O_{\lambda}(G)\leq\delta -1\), where \(\lambda^\prime\) is the restricted edge connectivity of \(G\). More refined bounds are given for regular graphs and edge transitive graphs. In addition, we also give the bound of \(O_{\lambda}(G)\) for the hierarchical product of graphs.

MSC:

05C40 Connectivity
PDFBibTeX XMLCite