Edge fault-tolerance analysis of maximally edge-connected graphs and super edge-connected graphs

Abstract Edge fault-tolerance of interconnection network is of significant important to the design and maintenance of multiprocessor systems. A connected graph G is maximally edge-connected (maximally-λ for short) if its edge-connectivity attains its minimum degree. G is super edge-connected (super-λ for short) if every minimum edge-cut isolates one vertex. The edge fault-tolerance of the maximally-λ (resp. super-λ) graph G with respect to the maximally-λ (resp. super-λ) property, denoted by m λ ( G ) (resp. S λ ( G ) ), is the maximum integer m for which G − S is still maximally-λ (resp. super-λ) for any edge subset S with | S | ≤ m . In this paper, we give upper and lower bounds on m λ ( G ) . Furthermore, we completely determine the exact values of m λ ( G ) and S λ ( G ) for vertex transitive graphs.