2024/01/28 by Ye, Hazhe, Tian, Yingzhi
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2401.15549
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 with at least 2 vertices. It was proved that if G is not a star and |V(G)|≥4, then λ′(G) exists and λ′(G)≤ξ(G), where ξ(G) is the minimum edge-degree of G. Thus 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\boxtimes H, is the graph with vertex set V(G)× V(H) and 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\boxtimes Pn, G\boxtimes Cn and G\boxtimes Kn, where Pn, Cn and Kn are the path, the cycle and the complete graph on n vertices, respectively. As corollaries, we give sufficient conditions for these strong product graphs G\boxtimes Pn, G\boxtimes Cn and G\boxtimes Kn to be maximally restricted edge-connected and super restricted edge-connected.