Edge Fault Tolerance of Cartesian Product Graphs on Super Restricted Edge Connectivity. (21st November 2017) - Wang, Shiying; Zhang, Guozhen; Feng, Kai
Abstract: 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 G i is a connected regular graph with δ i = δ ( G i ) = λ ( G i ) ≥ 4 for i = 1, 2, …, n, then ∑ i =1 n δ i − 2 ≤ S λ ′ ( G 1 × G 2 × ⋯ × G n ) ≤ ∑ i =1 n δ i − 1 .