Fault Tolerance of λ-Optimal Graphs

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 subset of E(G) with vertical bar S vertical bar <= 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' - delta, delta - 1} <= O-lambda(G) <= delta - 1, where lambda' 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.