Edge Fault Tolerance of Cartesian Product Graphs on Super Restricted Edge Connectivity. (21st November 2017)

• Record Type: Journal Article
• Authors: Wang, Shiying; Zhang, Guozhen; Feng, Kai
• Is Part Of: Computer journal. Volume 61:Number 5(2018)
• Page Start: 761
• Page End: 772
• Publication Date: 2017-11-21
• Subjects: interconnection network -- graph -- edge fault tolerance -- super restricted edge connectivity -- cartesian product graph; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxx109
• Languages: English
• ISSNs: 0010-4620

Abstract

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 .