The $g$-extra connectivity of the strong product of paths and cycles

Abstract

Let $G$ be a connected graph and $g$ be a non-negative integer. The $g$-extra connectivity of $G$ is the minimum cardinality of a set of vertices in $G$, if it exists, whose removal disconnects $G$ and leaves every component with more than $g$ vertices. The strong product $G_1⊠G_2$ of graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ is the graph with vertex set $V(G_1⊠G_2)=V_1\times V_2$, where two distinct vertices $(x_1,x_2),(y_1,y_2)\in V_1\times V_2$ are adjacent in $G_1⊠G_2$ if and only if $x_i=y_i$ or $x_i{y}_i\in E_i$ for $i=1,2$. In this paper, we obtain the $g$-extra connectivity of the strong product of two paths, the strong product of a path and a cycle, and the strong product of two cycles.