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

摘要

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.