Edge fault-tolerance of strongly Menger edge connected graphs

Abstract A connected graph G is strongly Menger edge connected (SM-λ for short) if any two of its vertices x , y are connected by min ⁡ { d ( x ) , d ( y ) } edge-disjoint paths, where d ( x ) is the degree of x. The maximum edge-fault-tolerant with respect to the SM-λ property of G, denoted by s m λ ( G ) , is the maximum integer m such that G − F is still SM-λ for any edge-set F with | F | ≤ m . In this paper, we give a sharp lower and upper bound for s m λ ( G ) , and give a characterization of the minimum upper bound. Furthermore, for k-regular graphs, we give some examples to show that s m λ ( G ) can reach every value between the lower bound and the upper bound when k is odd; show that s m λ ( G ) can reach every even value between the lower bound and the upper bound, and the only possible odd value is k − 1 if k is even. Moreover, we completely determine the exact value of s m λ ( G ) when G is a vertex-transitive graph or when it is an edge-transitive graph.