The 3-restricted Edge-Connectivity of Strong Product Graphs

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 ${\lambda }_3(G)$, is defined as the minimum cardinality among all 3-restricted edge-cuts if there are at least one; otherwise, ${\lambda }_3(G)=+\mathrm{\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 \{\mathrm{\mid }[X,V(G)\setminus X{]}_G\mathrm{\mid }\mathrm{\mid }X\subseteq V(G),\mathrm{\mid }X\mathrm{\mid }=3\text{ and }G[X]\text{ is connected}\}\mathrm{.}$ If ${\lambda }_3(G)={\xi }_3(G)$, then $G$ is said to be maximally 3-restricted edge-connected. The strong product of graphs $G$ and $H$, denoted by $G⊠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)\mathrm{\mid }{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⊠C_n$ is maximally 3-restricted edge-connected, and determine the 3-restricted edge-connectivity of $G⊠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.