The g-Extra Connectivity of the Strong Product of Paths and Cycles

Let G be a graph with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$. The $minimum$$degree$ of G is denoted by $\delta \left(G\right)$. A $vertex$$cut$ in G is a set of vertices whose deletion makes G disconnected. The $connectivity$$\kappa \left(G\right)$ of the graph G is the minimum order of a vertex cut in G if G is not a complete graph; otherwise $\kappa \left(G\right)=\left|V\right(G\left)\right|-1$. Usually, the topology structure of an interconnection network can be modeled by a graph G, where $V\left(G\right)$ represents the set of nodes and $E\left(G\right)$ represents the set of links connecting nodes in the network. Connectivity is used to measure the reliability the network, while it always underestimates the resilience of large networks.

To overcome this deficiency, Harary [1] generalized the concept of the classical connectivity $\kappa \left(G\right)$ as follows. Let $\mathcal{P}$ be a graph-theoretic property. A vertex set $S\subseteq V\left(G\right)$ is a $\mathcal{P}$-$cut$ if $G-S$ is disconnected and each component of $G-S$ has property $\mathcal{P}$. The $conditional$$connectivity$$\kappa (G;\mathcal{P})$ is the minimum cardinality of a $\mathcal{P}$-cut if G has at least one $\mathcal{P}$-cut. Later, Fàbrega and Fiol [2] introduced the concept of g-extra connectivity, which is a kind of conditional connectivity. Let g be a non-negative integer. If the vertex set $S\subseteq V\left(G\right)$ satisfies $G-S$ is disconnected and each component of $G-S$ has at least $g+1$ vertices, then S is called a g-$extra$$cut$. If G has at least one g-extra cut, then the g-$extra$$connectivity$ of G, denoted by ${\kappa }_g\left(G\right)$, is the the minimum cardinality of a g-extra cut. Otherwise, define ${\kappa }_g\left(G\right)=\infty$. If S is a g-extra cut in G with order ${\kappa }_g\left(G\right)$, then we call S a ${\kappa }_g$-$cut$. Since ${\kappa }_0\left(G\right)=\kappa \left(G\right)$ for any connected graph G that is not a complete graph, the g-extra connectivity can be seen as a generalization of the traditional connectivity. The authors in [3] pointed out that there is no polynomial-time algorithm for computing ${\kappa }_g$ for a general graph. Consequently, much of the work has been focused on the computing of the g-extra connectivity of some given graphs, see [3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] for examples.

Graph product is used to produce large graphs from small ones. There are many kinds of products, such as Cartesian product, direct product, strong product and lexicographic product. The $Cartesian$$product$ of two graphs $G_1$ and $G_2$, denoted by $G_1\square G_2$, is defined on the vertex sets $V\left(G_1\right)\times V\left(G_2\right)$, and $(x_1,y_1)(x_2,y_2)$ is an edge in $G_1\square G_2$ if and only if one of the following is true: (i) $x_1=x_2$ and $y_1{y}_2\in E\left(G_2\right)$; ($ii$) $y_1=y_2$ and $x_1{x}_2\in E\left(G_1\right)$.

For two graphs $G_1$ and $G_2$, the strong product $G_1⊠G_2$ is defined as follows: its vertex set is $V\left(G_1\right)\times V\left(G_2\right)$ and its edge set is $\left\{(x_1,x_2)(y_1,y_2)\right|$$x_1=x_2$ and $y_1{y}_2\in E\left(G_2\right)$; or $y_1=y_2$ and $x_1{x}_2\in E\left(G_1\right)$; or $x_1{x}_2\in E\left(G_1\right)$ and $y_1{y}_2\in E\left(G_2\right)\}$, where $(x_1,x_2),(y_1,y_2)\in V\left(G_1\right)\times V\left(G_2\right)$.

Špacapan [21] proved that for any nontrivial graphs $G_1$ and $G_2$, $\kappa (G_1\square G_2)=min$$\left\{\kappa \left(G_1\right)\right|V\left(G_2\right)|,\kappa \left(G_2\right)|V\left(G_1\right)|,\delta (G_1\square G_2)\}$. Lü, Wu, Chen and Lv [22] provided bounds for the 1-extra connectivity of the Cartesian product of two connected graphs. Tian and Meng [23] determined the exact values of the 1-extra connectivity of the Cartesian product for some class of graphs. In [24], Chen, Meng, Tian and Liu further studied the 2-extra connectivity and the 3-extra connectivity of the Cartesian product of graphs.

Brešar and Špacapan [25] determined the edge-connectivity of the strong products of two connected graphs. For the connectivity of the strong product graphs, Špacapan [26] obtained $Theorem 1$ in the following. Let $S_i$ be a vertex cut in $G_i$ for $i=1,2$, and let $A_i$ be a component of $G_i-S_i$ for $i=1,2$. Following the definitions in [26], $I=S_1\times V_2$ or $I=V_1\times S_2$ is called an I-set in $G_1⊠G_2$, and $L=(S_1\times A_2)\cup (S_1\times S_2)\cup (A_1\times S_2)$ is called an L-set in $G_1⊠G_2$.

Motivated by the results above, we will study the g-extra connectivity of the strong product graphs. In the next section, we introduce some definitions and lemmas. In Section 3, we will give 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. Conclusion will be given in Section 4.

For graph-theoretical terminology and notations not defined here, we follow [27]. Let G be a graph with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$. The $neighborhood$ of a vertex u in G is $N_G\left(u\right)=\{v\in V\left(G\right)|v\mathrm{is}\mathrm{adjacent}\mathrm{to}\mathrm{the}\mathrm{vertex}u\}$. Let A be a subset of $V\left(G\right)$, the neighborhood of A in G is $N_G\left(A\right)=\{v\in V\left(G\right)\backslash A|v\mathrm{is}\mathrm{adjacent}\mathrm{to}\mathrm{a}\mathrm{vertex}\mathrm{in}A\}$. The subgraph induced by A in G is denoted by $G\left[A\right]$. We use $P_n$ to denote the path with order n and $C_n$ to denote the cycle with order n.

Let $G_1$ and $G_2$ be two graphs. Define two natural projections $p_1$ and $p_2$ on $V\left(G_1\right)\times V\left(G_2\right)$ as follows: $p_1(x,y)=x$ and $p_2(x,y)=y$ for any $(x,y)\in V\left(G_1\right)\times V\left(G_2\right)$. The subgraph induced by $\left\{(u,y)\right|u\in V\left(G_1\right)\}$ in $G_1⊠G_2$, denoted by $G_{1y}$, is called a $G_1$-$layer$ in $G_1⊠G_2$ for each vertex $y\in V\left(G_2\right)$. Analogously, the subgraph induced by $\left\{(x,v)\right|v\in V\left(G_2\right)\}$ in $G_1⊠G_2$, denoted by ${}_x{G}_2$, is called a $G_2$-$layer$ in $G_1⊠G_2$ for each vertex $x\in V\left(G_1\right)$. Clearly, a $G_1$-layer in $G_1⊠G_2$ is isomorphic to $G_1$, and a $G_2$-layer in $G_1⊠G_2$ is isomorphic to $G_2$.

Let $S\subseteq V(G_1⊠G_2)$. For any $x\in V\left(G_1\right)$, denote $S\cap V\left({}_x{G}_2\right)$ by ${}_{x}S$, and analogously, for any $y\in V\left(G_2\right)$, denote $S\cap V\left(G_{1y}\right)$ by $S_y$. Furthermore, we use $\overline{{}_{x}S}=V\left({}_x{G}_2\right)\backslash {}_{x}S$ and $\overline{S_y}=V\left(G_{1y}\right)\backslash S_y$. By almost the same argument as the proof of the second paragraph of $Theorem$ 3.2 in [26], we can obtain the following lemma. For completeness, we also address the proof here.

Let H be a subgraph of $G_1⊠G_2$. For the sake of simplicity, we use ${}_{x}H$ instead of ${}_{x}V\left(H\right)$ to represent $V\left(H\right)\cap V\left({}_x{G}_2\right)$ for any $x\in V\left(G_1\right)$ and $H_y$ to represent $V\left(H\right)\cap V\left(G_{1y}\right)$ for any $y\in V\left(G_2\right)$. Since ${\kappa }_g(P_1⊠P_n)=1$ for $g\le \lfloor \frac{n-1}{2}\rfloor -1$ and ${\kappa }_g(P_2⊠P_n)=2$ for $g\le 2\lfloor \frac{n-1}{2}\rfloor -1$, we assume $m,n\ge 3$ in the following theorem.

Now, it is sufficient to prove ${\kappa }_g\left(G\right)\ge$ min$\{m,n,\lceil 2\sqrt{g+1}\rceil +1\}$. Assume S is a ${\kappa }_g$-cut of G. We consider two cases in the following.

Case 1.${}_{x}S\ne \varnothing$ for all $x\in V\left(P_m\right)$, or $S_y\ne \varnothing$ for all $y\in V\left(P_n\right)$.

Assume ${}_{x}S\ne \varnothing$ for all $x\in V\left(P_m\right)$. By Lemma 2.1, $\left|S\right|={\sum }_{x\in V\left(P_m\right)}|{}_{x}S|\ge \kappa \left(P_n\right)\left|V\left(P_m\right)\right|=m$. Analogously, if $S_y\ne \varnothing$ for all $y\in V\left(P_n\right)$, then $\left|S\right|={\sum }_{y\in V\left(P_n\right)}|S_y|\ge \kappa \left(P_m\right)\left|V\left(P_n\right)\right|=n$.

Case 2. There exist a vertex $x_a\in V\left(P_m\right)$ and a vertex $y_b\in V\left(P_n\right)$ such that ${}_{x_a}S=S_{y_b}=\varnothing$.

By the assumption ${}_{x_a}S=S_{y_b}=\varnothing$, we know $V\left({}_{x_a}{G}_2\right)$ and $V\left(G_{1y_b}\right)$ are contained in a component $H^{\prime }$ of $G-S$. Let H be another component of $G-S$. Let $p_1\left(V\left(H\right)\right)=\{x_{s+1},x_{s+2},\dots ,x_{s+k}\}$ and $p_2\left(V\left(H\right)\right)=\{y_{t+1},y_{t+2},\dots ,y_{t+h}\}$. Without loss of generality, assume $s+k<a$ and $t+h<b$. Clearly, $\left|V\right(H\left)\right|\le kh$. Since S is a ${\kappa }_g$-cut, we have $N_G\left(V\left(H\right)\right)=S$ and $\left|V\right(H\left)\right|\ge g+1$. If we can prove $|N_G\left(V\left(H\right)\right)|\ge k+h+1$, then ${\kappa }_g\left(G\right)=\left|S\right|=|N_G\left(V\left(H\right)\right)|\ge k+h+1\ge 2\sqrt{kh}+1\ge 2\sqrt{g+1}+1$ and the theorem holds. Thus, we only need to show that $|N_G\left(V\left(H\right)\right)|\ge k+h+1$ in the remaining proof.

Let $(x_{s+i},y_{d_i})$ be the vertex in ${}_{x_{s+i}}H$ such that $d_i$ is maximum for $i=1,\dots ,k$, and let $(x_{r_j},y_{t+j})$ be the vertex in $H_{y_{t+j}}$ such that $r_j$ is maximum for $j=1,\dots ,h$. Denote $D=\{(x_{s+1},y_{d_1}),\dots ,(x_{s+k},y_{d_k})\}$ and $R=\{(x_{r_1},y_{t+1}),\dots ,(x_{r_h},y_{t+h})\}$. For the convenience of counting, we will construct an injective mapping f from $D\cup R$ to $N_G(V\left(H\right)\backslash \left\{(x_{s+k+1},y_{d_k+1})\right\}$. Although D and R may have common elements, we consider the elements in D and R to be different in defining the mapping f below.

First, the mapping f on D is defined as follows.

Denote $F_1=\{(x_{s+1},y_{d_1+1}),\dots ,(x_{s+k},y_{d_k+1})\}$.

Second, for each vertex $(x_{r_j},y_{t+j})$ satisfying $(x_{r_j+1},y_{t+j})\notin F_1$, define $f\left((x_{r_j},y_{t+j})\right)=(x_{r_j+1},y_{t+j})$.

If $(x_{r_j},y_{t+j})$ satisfies $(x_{r_j+1},y_{t+j})\notin F_1$ for any $j\in \{1,\dots ,h\}$, then we are done. Otherwise, for each $(x_{r_{j^{\prime }}},y_{t+j^{\prime }})$ satisfying $(x_{r_{j^{\prime }}+1},y_{t+j^{\prime }})\in F_1$, we give the definition as follows. By the definitions of D and R, we have $(x_{r_{j^{\prime }}+1+i},y_{t+j^{\prime }+j})\notin V\left(H\right)$ for all $i,j\ge 0$, and $\{(x_{r_{j^{\prime }}},y_{t+j^{\prime }}),\dots ,(x_{r_{j^{\prime }}},y_{d_{r_{j^{\prime }}-s}})\}\subseteq R$ (see Figure 1 for an illustration). Now, we define $f\left((x_{r_{j^{\prime }}},y_{t+j^{\prime }})\right)=(x_{r_{j^{\prime }}+1},y_{t+j^{\prime }+1})$ and change the images of $(x_{r_{j^{\prime }}},y_{t+j^{\prime }+1}),\dots ,(x_{r_{j^{\prime }}},y_{d_{r_{j^{\prime }}-s}})$ to $(x_{r_{j^{\prime }}+1},y_{t+j^{\prime }+2}),\dots ,(x_{r_{j^{\prime }}+1},y_{d_{r_{j^{\prime }}-s}+1})$, respectively. The images of f on R are well-defined.

Finally, we have an injective mapping f from $D\cup R$ to $N_G(V\left(H\right)\backslash \left\{(x_{s+k+1},y_{d_k+1})\right\}$. Then ${\kappa }_g\left(G\right)=\left|S\right|=|N_G\left(V\left(H\right)\right)|\ge |D|+|R|+1\ge k+h+1\ge 2\sqrt{kh}+1\ge 2\sqrt{g+1}+1$. The proof is thus complete.

Since ${\kappa }_g(C_3⊠P_n)=3$ for $g\le 3\lfloor \frac{n-1}{2}\rfloor -1$, we assume $m\ge 4$ in the following theorem.

Now, it is sufficient to prove ${\kappa }_g\left(G\right)\ge$ min$\{m,2n,\lceil 2\sqrt{2(g+1)}\rceil +2\}$. Assume S is a ${\kappa }_g$-cut of G. We consider two cases in the following.

Case 1.${}_{x}S\ne \varnothing$ for all $x\in V\left(C_m\right)$, or $S_y\ne \varnothing$ for all $y\in V\left(P_n\right)$.

Assume ${}_{x}S\ne \varnothing$ for all $x\in V\left(C_m\right)$. By $Lemma$ 2.1, $\left|S\right|={\sum }_{x\in V\left(C_m\right)}|{}_{x}S|\ge \kappa \left(P_n\right)\left|V\left(C_m\right)\right|$$=m$. Analogously, if $S_y\ne \varnothing$ for all $y\in V\left(P_n\right)$, then $\left|S\right|={\sum }_{y\in V\left(P_n\right)}|S_y|\ge \kappa \left(C_m\right)\left|V\left(P_n\right)\right|=2n$.

Case 2. There exist a vertex $x_a\in V\left(C_m\right)$ and a vertex $y_b\in V\left(P_n\right)$ such that ${}_{x_a}S=S_{y_b}=\varnothing$.

By the assumption ${}_{x_a}S=S_{y_b}=\varnothing$, we know $V\left({}_{x_a}{G}_2\right)$ and $V\left(G_{1y_b}\right)$ are contained in a component $H^{\prime }$ of $G-S$. Let H be another component of $G-S$. Let $p_1\left(V\left(H\right)\right)=\{x_{s+1},x_{s+2},\dots ,x_{s+k}\}$ and $p_2\left(V\left(H\right)\right)=\{y_{t+1},y_{t+2},\dots ,y_{t+h}\}$. Without loss of generality, assume $s+k<a$ and $t+h<b$. Clearly, $\left|V\right(H\left)\right|\le kh$. Since S is a ${\kappa }_g$-cut, we have $N_G\left(V\left(H\right)\right)=S$ and $\left|V\right(H\left)\right|\ge g+1$. If we can prove $|N_G\left(V\left(H\right)\right)|\ge k+2h+2$, then ${\kappa }_g\left(G\right)=\left|S\right|=|N_G\left(V\left(H\right)\right)|\ge k+2h+2\ge 2\sqrt{2kh}+2\ge 2\sqrt{2(g+1)}+2$ and the theorem holds. Thus, we only need to show that $|N_G\left(V\left(H\right)\right)|\ge k+2h+2$ in the remaining proof.

Let $(x_{s+i},y_{d_i})$ be the vertex in ${}_{x_{s+i}}H$ such that $d_i$ is maximum for $i=1,\dots ,k$, and let $(x_{l_j},y_{t+j})$ and $(x_{r_j},y_{t+j})$ be the vertices in $H_{y_{t+j}}$ such that $l_j$ and $r_j$ are listed in the foremost and in the last along the sequence $(a+1,\dots ,m-1,0,1,\dots ,a-1)$, respectively, for $j=1,\dots ,h$. Denote $D=\{(x_{s+1},y_{d_1}),\dots ,(x_{s+k},y_{d_k})\}$, $L=\{(x_{l_1},y_{t+1}),\dots ,(x_{l_h},y_{t+h})\}$ and $R=\{(x_{r_1},y_{t+1}),\dots ,(x_{r_h},y_{t+h})\}$. For the convenience of counting, we will construct an injective mapping f from $D\cup L\cup R$ to $N_G(V\left(H\right)\backslash \{(x_s,y_{d_1+1}),(x_{s+k+1},y_{d_k+1})\}$. Although D, L and R may have common elements, we consider the elements in D, L and R to be different in defining the mapping f below.

First, the mapping f on D is defined as follows.

Denote $F_1=\{(x_{s+1},y_{d_1+1}),\dots ,(x_{s+k},y_{d_k+1})\}$.

Second, for each vertex $(x_{r_j},y_{t+j})$ satisfying $(x_{r_j+1},y_{t+j})\notin F_1$, define $f\left((x_{r_j},y_{t+j})\right)=(x_{r_j+1},y_{t+j})$.

If $(x_{r_j},y_{t+j})$ satisfies $(x_{r_j+1},y_{t+j})\notin F_1$ for any $j\in \{1,\dots ,h\}$, then we are done. Otherwise, for each $(x_{r_{j^{\prime }}},y_{t+j^{\prime }})$ satisfying $(x_{r_{j^{\prime }}+1},y_{t+j^{\prime }})\in F_1$, we give the definition as follows. By the definitions of D and R, we have $\{(x_{r_{j^{\prime }}},y_{t+j^{\prime }}),\dots ,(x_{r_{j^{\prime }}},y_{d_{r_{j^{\prime }}-s}})\}\subseteq R$. Now, we define $f\left((x_{r_{j^{\prime }}},y_{t+j^{\prime }})\right)=(x_{r_{j^{\prime }}+1},y_{t+j^{\prime }+1})$ and change the images of $(x_{r_{j^{\prime }}},y_{t+j^{\prime }+1}),\dots ,(x_{r_{j^{\prime }}},y_{d_{r_{j^{\prime }}-s}})$ to $(x_{r_{j^{\prime }}+1},y_{t+j^{\prime }+2}),\dots ,(x_{r_{j^{\prime }}+1},y_{d_{r_{j^{\prime }}-s}+1})$, respectively. The mapping f on R is defined well.

Third, for each vertex $(x_{l_j},y_{t+j})$ satisfying $(x_{l_j-1},y_{t+j})\notin F_1$, define $f\left((x_{l_j},y_{t+j})\right)=(x_{l_j-1},y_{t+j})$.

If $(x_{l_j},y_{t+j})$ satisfies $(x_{l_j-1},y_{t+j})\notin F_1$ for any $j\in \{1,\dots ,h\}$, then we are done. Otherwise, for each $(x_{l_{j^{\prime }}},y_{t+j^{\prime }})$ satisfying $(x_{l_{j^{\prime }}-1},y_{t+j^{\prime }})\in F_1$. By the definitions of D and L, we have $\{(x_{l_{j^{\prime }}},y_{t+j^{\prime }}),\dots ,(x_{l_{j^{\prime }}},y_{d_{l_{j^{\prime }}-s}})\}\subseteq L$. Now, we define $f\left((x_{l_{j^{\prime }}},y_{t+j^{\prime }})\right)=(x_{l_{j^{\prime }}-1},y_{t+j^{\prime }+1})$ and change the images of $(x_{l_{j^{\prime }}},y_{t+j^{\prime }+1}),\dots ,(x_{l_{j^{\prime }}},y_{d_{l_{j^{\prime }}-s}})$ to $(x_{r_{j^{\prime }}-1},y_{t+j^{\prime }+2}),\dots ,(x_{l_{j^{\prime }}-1},$$y_{d_{r_{j^{\prime }}-s}+1})$, respectively. The definition of f on L is complete.

Finally, we construct an injective mapping f from $D\cup L\cup R$ to $N_G(V\left(H\right)\backslash$$\{(x_s,y_{d_1+1}),(x_{s+k+1},y_{d_k+1})\}$. Then ${\kappa }_g\left(G\right)=\left|S\right|=|N_G\left(V\left(H\right)\right)|\ge |D|+|L|+|R|+2\ge k+2h+1\ge 2\sqrt{2kh}+2\ge 2\sqrt{2(g+1)}+2$. The proof is thus complete. □

Since ${\kappa }_g(C_3⊠C_n)=6$ for $g\le 3\lfloor \frac{n-2}{2}\rfloor -1$, we assume $m,n\ge 4$ in the following theorem.