The 3-restricted Edge-Connectivity of Strong Product Graphs

Abstract

An edge subset \( S \subseteq E(G) \) is called a 3-restricted edge-cut if $G-S$ is disconnected and each component of \( G - S \) contains at least three vertices. The 3-restricted edge-connectivity of a graph \( G \), denoted by \( λ_3(G) \), is defined as the minimum cardinality among all 3-restricted edge-cuts if there are at least one; otherwise, \( λ_3(G) = +\infty \). It is proved that ${\lambda }_3(G)\le {\xi }_3(G)$ if $G$ has a 3-restricted edge-cut, where ${\xi }_3(G)=\min \{|[X,V(G)\setminus X{]}_G||X\subseteq V(G),|X|=3\text{ and }G[X]\text{ is connected}\}.$ If \( λ_3(G) = ξ_3(G) \), then \( G \) is said to be maximally 3-restricted edge-connected. The strong product of graphs \( G \) and \( H \), denoted by \( G \boxtimes H \), is the graph with the vertex set $V(G)\times V(H)$ and the edge set $\{(x_1,y_1)(x_2,y_2)|x_1=x_2\text{ and }{y}_1{y}_2\in E(H);\text{ or }{y}_1=y_2$ and $x_1{x}_2\in E(G)$; or $x_1{x}_2\in E(G)$ and $y_1{y}_2\in E(H)\}$. In this paper, we prove that \( G \boxtimes C_{n} \) is maximally 3-restricted edge-connected, and determine the 3-restricted edge-connectivity of \( G \boxtimes K_{n} \), where \( G \) is a maximally edge-connected graph, \( C_{n} \) and \( K_{n} \) are the cycle and the complete graph of order \( n \), respectively.