Edge Fault Tolerance of Cartesian Product Graphs on Super Restricted Edge Connectivity
Shiying Wang, Guozhen Zhang, Kai Feng · The Computer Journal · 2017
The cartesian product is a very effective method for designing large-scale interconnection networks. The super-λ′ property is an index to measure the reliability of networks. Let G=(V,E) be a connected graph. An edge set S⊆E is a restricted edge cut if G−S is disconnected and every component of G−S has at least two vertices. A graph G is super-λ′ if every minimum restricted edge cut of G isolates one edge. Fault tolerance of networks is an important issue. The edge fault tolerance Sλ′(G) of a super-λ′ graph G on the super-λ′ property is the maximum integer m for which G−S is still super-λ′ for any edge set S⊆E with |S|≤m. In this paper, we give the lower and upper bounds on Sλ′(G) for the cartesian product of graphs. More refined bounds on Sλ′(G) are obtained for the cartesian product of regular graphs. In particular, exact values of Sλ′(G) are determined for some special classes of the cartesian product graphs. For example, if Gi is a connected regular graph with δi=δ(Gi)=λ(Gi)≥4 for i=1,2,…,n, then ∑i=1nδi−2≤Sλ′(G1×G2×⋯×Gn)≤∑i=1nδi−1.