The Restricted Edge-Connectivity of Strong Product Graphs

The restricted edge-connectivity of a connected graph G, denoted by λ′ (G), if it exists, is the minimum cardinality of a set of edges whose deletion makes G disconnected, and each component has at least two vertices. It was proved that λ′ (G) exists if and only if G has at least four vertices and G is not a star. In this case, a graph G is called maximally restricted edge-connected if λ′ (G) =ξ (G), and a graph G is called super restricted edge-connected if each minimum restricted edge-cut isolates an edge of G. The strong product of graphs G and H, denoted by G⊠H, is the graph with the vertex set V (G) ×V (H) and the edge set (x1, y1) (x2, y2) |x1=x2 and y1y2∈E (H) ; or y1=y2 and x1x2∈E (G) ; or x1x2∈E (G) and y1y2∈E (H). In this paper, we determine, for any nontrivial connected graph G, the restricted edge-connectivity of G⊠Pn, G⊠Cn and G⊠Kn, where Pn, Cn and Kn are the path, cycle and complete graph of order n, respectively. As corollaries, we give sufficient conditions for these strong product graphs G⊠Pn, G⊠Cn and G⊠Kn to be maximally restricted edge-connected and super restricted edge-connected.