Vulnerability of super edge-connected networks

When the underlying topology of an interconnection network is modeled by a connected graph G, the connectivity of G   is an important measurement for reliability and fault tolerance of the network. For a given integer h≥0h≥0, a subset F of edges in a connected graph G is an h  -extra edge-cut if G−FG−F is disconnected and every component has more than h vertices. The h  -extra edge-connectivity λ(h)(G)λ(h)(G) of G is defined as the minimum cardinality over all h-extra edge-cuts of G. A graph G  , if λ(h)(G)λ(h)(G) exists, is super-λ(h)λ(h) if every minimum h-extra edge-cut of G   isolates at least one connected subgraph of order h+1h+1. The persistence ρ(h)(G)ρ(h)(G) of a super-λ(h)λ(h) graph G is the maximum integer m   for which G−FG−F is still super-λ(h)λ(h) for any set F⊆E(G)F⊆E(G) with |F|≤m|F|≤m. Hong et al. (2012) [12] showed that min{λ(1)(G)−δ(G)−1,δ(G)−1}≤ρ(0)(G)≤δ(G)−1min{λ(1)(G)−δ(G)−1,δ(G)−1}≤ρ(0)(G)≤δ(G)−1, where δ(G)δ(G) is the minimum vertex-degree of G  . This paper shows that min{λ(2)(G)−ξ(G)−1,δ(G)−1}≤ρ(1)(G)≤δ(G)−1min{λ(2)(G)−ξ(G)−1,δ(G)−1}≤ρ(1)(G)≤δ(G)−1, where ξ(G)ξ(G) is the minimum edge-degree of G. In particular, for a k  -regular super-λ(1)λ(1) graph G  , ρ(1)(G)=k−1ρ(1)(G)=k−1 if λ(2)(G)λ(2)(G) does not exist or G   is super-λ(2)λ(2) and triangle-free, from which the exact values of ρ(1)(G)ρ(1)(G) are determined for some well-known networks.