The g-Good-Neighbor Connectivity of Some Cartesian Product Graphs

Yinkui Li, Ting Xie, Xiaoxiao Qin

Department of Mathematics and Statistics, Qinghai Nationalities University, Xining, China.

DOI: 10.4236/ojdm.2023.131003                

Abstract

The g-good-neighbor connectivity of G is a generalization of the concept of connectivity, which is just for, and an important parameter in measuring the fault tolerance and reliability of interconnection network. Many well-known networks can be constructed by the Cartesian products of some simple graphs. In this paper, we determine the g-good-neighbor connectivity of some Cartesian product graphs. We give the exact value of g-good-neighbor connectivity of the Cartesian product of two complete graphs and for , mesh for , cylindrical grid and torus for .

Keywords

Connectivity, The g-Good-Neighbor Connectivity, Cartesian Product

1. Introduction

We call a multiprocessor system fault-tolerant if it can keep working in case of failure. In the beginning, connectivity and edge connectivity of graph were used to measure the fault-tolerant of system. Later, people found that these two parameters had some defects since they assume that all adjacent vertices or edges of the same vertex may fail at the same time, which is unlikely in real networks. In 1996, Fàbrega and Fiol [1] made some improvements in the connectivity and proposed the concept of g-good neighbor connectivity to measure the fault-tolerant of the multiprocessor.

Let $G=\left(V,E\right)$ be a given connected graph with vertices set $V\left(G\right)$ and edges set $E\left(G\right)$. If u and v are vertices of a graph G, we say u is adjacent to v if there is an edge between u and v. We also say u and v are neighbors. For a vertex $v\in V$, we by $N\left(v\right)$ denote the set of neighbors of v and by $N\left(S\right)$ denote the set of neighbors of every vertex in S. A set $F\subseteq V$ is called a g-good-neighbor faulty set of G if $\left|N\left(v\right)\cap \left(V\backslash F\right)\right|\ge g$ for every vertex v in $V-F$. A g-good- neighbor cut of G is a g-good-neighbor faulty set F such that $G-F$ is disconnected. We call the minimum cardinality of g-good-neighbor cuts the g-good- neighbor connectivity of G, denoted by ${\kappa }^g\left(G\right)$. Clearly, ${\kappa }^0\left(G\right)=\kappa \left(G\right)$ for any graph G.

In 2012, Peng et al. [2] determined the g-good-neighbor conditional diagnosability of hypercube under the PMC model. In 2016, Wang et al. [3] showed that 2-good-neighbor connectivity of bubble-Sort Star Graph BS_n is $8n-22$ for $n\ge 5$ and the 2-good-neighbor connectivity of BS₄ is 8. In 2017, Ren and Wang [4] [5] determined the 1-good-neighbor connectivity of locally twisted cubes and the g-good-neighbor diagnosability of locally twisted cubes, respectively. In 2018, Wei and Xu [6] determined the 1, 2-good-neighbor conditional diagnosabilities of regular graphs. In 2020, Wang and Wang [7] showed that the 3-good-neighbor connectivity of Modified Bubble-Sort Graphs MBn is $8n-24$ for $n\ge 6$. Motivated by these researches, notice that the Cartesian product is an important method to obtain large graphs from smaller ones for designing large-scale interconnection networks [8] [9] [10]. In this paper, we plan to determine the g-good-neighbor connectivity of the Cartesian product of graphs.

The Cartesian product of two graphs $G_1$ and $G_2$ is the graph $G_1\times G_2$ whose vertex set is the Cartesian product of the sets $V\left(G_1\right)$ and $V\left(G_2\right)$. Two vertices $\left(u_1,v_1\right)$ and $\left(u_2,v_2\right)$ are adjacent in $G_1\times G_2$ precisely when either $u_1=u_2$ and $v_1{v}_2\in E\left(G_2\right)$ or $v_1=v_2$ and $u_1{u}_2\in E\left(G_1\right)$. In fact, many well-known networks can be constructed by the Cartesian products of some simple graphs and the Cartesian product preserves many nice properties such as regularity, existence of Hamilton cycles and Euler circuits, and transitivity of the initial graphs. See [11] [12] [13].

In this paper, we determine the g-good-neighbor connectivity of the Cartesian

product of two complete graphs $K_m$ and $K_n$ for $0\le g\le \lfloor \frac{m+n-4}{2}\rfloor$, mesh

$P_m\times P_n$ for $0\le g\le 2$, cylindrical grid $P_m\times C_n$ and torus $C_m\times C_n$ for $0\le g\le 3$. As usual, we by $\Delta \left(G\right)$ and $\kappa \left(G\right)$ denote the maximum degree and the connectivity of a graph G, respectively. Use $P_n$, $C_n$ and $K_n$ denote path, cycle and complete graph with order n.

2. Main Results

In this section, we determine the g-good-neighbor connectivity of Cartesian product of two complete graphs $K_m$ and $K_n$, mesh, cylindrical grid and torus.

Lemma 2.1. [14] Let G be a connected graph and g be an integer. Then ${\kappa }^g\left(G\right)\le {\kappa }^{g+1}\left(G\right)$.

Theorem 2.2. Let $K_m\times K_n$ be Cartesian product of complete graph $K_m$ and

$K_n$ with $1\le m\le n$ and g be non-negative integer with $0\le g\le \lfloor \frac{m+n-4}{2}\rfloor$ . Then the g-good-neighbor connectivity of $K_m\times K_n$ is

1) For $g=0$, ${\kappa }^g\left(K_m\times K_n\right)=\kappa \left(K_m\times K_n\right)=m+n-2$.

2)For $1\le g\le \lfloor \frac{m+n-4}{2}\rfloor$,

${\kappa }^g\left(K_m\times K_n\right)=(\begin{array}{ll}\lceil m\left(g+2\right)-\frac{{\left(m+2g+4-n\right)}^2}{8}\rceil ,\hfill & n\ge 2g+8-3m;\hfill \\ \left(m-1\right)\left(m-2g-6+n\right)+m\left(g+2\right),\hfill & n<2g+8-3m.\hfill \end{array}$

Proof. Let $G=K_m\times K_n$ with $V\left(G\right)=\left\{w_{ij}|w_{ij}=\left(u_i,v_j\right)|u_i\in V\left(K_m\right),v_j\in V\left(K_n\right)\right\}$ for $1\le i\le m$ and $1\le j\le n$. Consider G is $m+n-2$ regular, thus, we have ${\kappa }^0\left(G\right)=\kappa \left(G\right)=m+n-2$. Suppose F is a g-good neighbor cut set of G with minimum cardinality and let $G-F=G_1\cup G_2\cup \cdots \cup G_p$.

Now, we further show that $G_k=K_{m_k}\times K_{n_k}$ with $m_k\le n_k$ for $k=1,2,\cdots ,p$. In fact, it is enough if we show that whenever $\left(u_i\mathrm{,}{v}_r\right)\mathrm{,}\left(u_i\mathrm{,}{v}_s\right)\mathrm{,}\left(u_j\mathrm{,}{v}_r\right)\in V\left(G_k\right)$, then $\left(u_j\mathrm{,}{v}_s\right)\in V\left(G_k\right)$. On the contrary, if $\left(u_j\mathrm{,}{v}_s\right)\in V\left(G-G_k\right)$, then we by the definition of $K_m\times K_n$ get $\left(u_j\mathrm{,}{v}_s\right)\in F$. Let $F^{\prime }=F-\left(u_j,v_s\right)$, then $\left(u_j\mathrm{,}{v}_s\right)$ is adjacent with $\left(u_i\mathrm{,}{v}_s\right)\mathrm{,}\left(u_j\mathrm{,}{v}_r\right)$ in $G-F^{\prime }$ and $\left[G_k\cup \left\{\left(u_j\mathrm{,}{v}_s\right)\right\}\right]$ is a component of $G-F^{\prime }$ such that $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F^{\prime }\right)\right|\ge g$ for every $v\in V\left(G\right)\backslash F$. This implies $F^{\prime }$ is also a g-good neighbor cut set of G with $\left|F^{\prime }\right|=\left|F\right|-1$. This contradicts to the fact F is of minimum cardinality. So, we have $G_k=K_{m_k}\times K_{n_k}$ with $m_k\le n_k$ for $k=1,2,\cdots ,p$. Further, we by the minimality of F know that $G-F$ has exactly two components. This means $G-F=\left(K_{m_1}\times K_{n_1}\right)\cup \left(K_{m_2}\times K_{n_2}\right)$.

Notice that F is a g-good neighbor cut set of G, we have $m_1+n_1\ge g+2$ and $m_2+n_2=g+2$. Combine this with $m_1=m-m_2$, $n_1=n-n_2$, we get

$m+n\ge 2\left(g+2\right)$, then $g\le \lfloor \frac{m+n}{2}\rfloor -2$. Thus, we have

$\begin{array}{c}\left|F\right|=\min \left\{m_1{n}_2+m_2{n}_1\right\}\\ =\min \left\{\left(m-m_2\right)n_2+m_2\left(n-n_2\right)\right\}\\ =\min \left\{\left(m-2m_2\right)\left(g+2-m_2\right)+n{m}_2\right\}\\ =\min \left\{2m_2^2-\left(m+2g+4-n\right)m_2+m\left(g+2\right)\right\}.\end{array}$

Notice that $2n_1\ge m_1+n_1\ge g+2$, we have $n_1\ge \frac{g+2}{2}$. By $m_2+n_2=g+2$ and $m_1=m-m_2$, $n_1=n-n_2$, we get $m_1+n_1=m+n-\left(g+2\right)$. So $m_1\le m+n-\frac{3\left(g+2\right)}{2}$. Thus $\frac{3\left(g+2\right)}{2}-n\le m_2\le m-1$.

Now, let $f\left(x\right)=2x^2-\left(m+2g+4-n\right)x+m\left(g+2\right)$, the following we determine the minimum value of $f\left(x\right)$ in interval $\left[\frac{3\left(g+2\right)}{2}-n\mathrm{,}m-1\right]$.

By $2n\ge m+n\ge 2\left(g+2\right)$, we have $n\ge g+2$. Thus

$\frac{m+2g+4-n}{4}-\left(\frac{3\left(g+2\right)}{2}-n\right)=\frac{m-n}{4}+n-g-2\ge 0$. By comparing the difference between $\frac{m+2g+4-n}{4}$ and $m-1$, we discuss the minimum value of $f\left(x\right)$.

If $n>2g+8-3m$, let $m+2g+4-n=t$, then $\min f\left(x\right)=$ $f\left(\frac{m+2g+4-n}{4}\right)=f\left(\frac{t}{4}\right)=2{\left(\frac{t}{4}\right)}^2-\frac{t^2}{4}+m\left(g+2\right)=\lceil m\left(g+2\right)-\frac{t^2}{8}\rceil$ ;

If $n\le 2g+8-3m$, then $\min f\left(x\right)=f\left(m-1\right)=2{\left(m-1\right)}^2-\left(m+2g+4-n\right)$ $\left(m-1\right)+m\left(g+2\right)=\left(m-1\right)\left(m-2g-6+n\right)+m\left(g+2\right)$.

By the above analysis, we get

${\kappa }^g\left(K_m\times K_n\right)=\left|F\right|=(\begin{array}{ll}\lceil m\left(g+2\right)-\frac{{\left(m+2g+4-n\right)}^2}{8}\rceil ,\hfill & n>2g+8-3m;\hfill \\ \left(m-1\right)\left(m-2g-6+n\right)+m\left(g+2\right),\hfill & n\le 2g+8-3m.\hfill \end{array}$

This completes the proof.

Example 1. The 1-good-neighbor connectivity of $K_3\times K_4$ is 6 with $F=\left\{w_{12},w_{13},w_{21},w_{24},w_{31},w_{34}\right\}$, which is shown in Figure 1.

Theorem 2.3. Let g, m and n be non-negative integers with $n\ge m\ge 2$ . Then the g-good-neighbor connectivity of mesh $P_m\times P_n$ is

1) For $g=0$, ${\kappa }^g\left(P_m\times P_n\right)=\kappa \left(P_m\times P_n\right)=2$.

2) For $g=1$, ${\kappa }^g\left(P_m\times P_n\right)=(\begin{array}{ll}2,\hfill & m=2;\hfill \\ 3,\hfill & m\ge 3.\hfill \end{array}$

3)For $g=2$, ${\kappa }^g\left(P_m\times P_n\right)=(\begin{array}{ll}m,\hfill & 2\le m\le 4,n\ge 5;\hfill \\ 8,\hfill & m=n=4;\hfill \\ 4,\hfill & m,n\ge 5.\hfill \end{array}$

Proof. Let $P_m\times P_n=G$ with $V\left(P_m\right)=\left\{u_1,u_2,\cdots ,u_m\right\}$ and $V\left(P_n\right)=\left\{v_1,v_2,\cdots ,v_n\right\}$. Then $V\left(G\right)=\left\{w_{ij}|w_{ij}=\left(u_i\mathrm{,}{v}_j\right)\mathrm{<mo>\; |\; </mo>}{u}_i\in V\left(P_m\right)\text{and}{v}_j\in V\left(P_n\right)\right\}$. Suppose F is a vertex cut set of G, notice that the minimum degree of $G-F$ is always less than 3, so $g=0,1,2$ and by the connectivity $\kappa \left(G\right)=2$ we have ${\kappa }^0\left(G\right)=2$. The following we by distinguishing cases to determine ${\kappa }^g\left(G\right)$.

Figure 1. ${\kappa }^1\left(K_3\times K_4\right)=6$.

Case 1. $g=1$.

$g=1$ means $n\ne 2$, so $n\ge 3$.

Subcase 1. $m=2$.

By Lemma 2.1, we have ${\kappa }^1\left(G\right)\ge {\kappa }^0\left(G\right)=2$. On the other hand, let $F=\left\{w_{1j}\mathrm{,}{w}_{2j}\right\}$ for $j=2$ or $n-1$. It is clear that $G-F$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F\right)\right|\ge 1$ for every $v\in V\left(G\right)\backslash F$. By the definition of g-good- neighbor connectivity, we have ${\kappa }^1\left(G\right)\le \left|F\right|=2$. Therefore, we get ${\kappa }^1\left(G\right)=2$.

Subcase 2. $m\ge 3$.

First, let $F=\left\{w_{12}\mathrm{,}{w}_{22}\mathrm{,}{w}_{31}\right\}$. Clearly, $G-F$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F\right)\right|\ge 1$ for every $v\in G-F$, so we have ${\kappa }^1\left(G\right)\le \left|F\right|=3$. On the other hand, suppose $F^{\prime }\subset V\left(G\right)$ is a vertex cut set of G such that $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F^{\prime }\right)\right|\ge 1$ for every $v\in V\left(G\right)\backslash F^{\prime }$. Then $G-F^{\prime }$ has a component C with $\left|C\right|\ge 2$ and the minimum degree of C is $\delta \left(C\right)=1$. Further, we have $\left|F^{\prime }\right|\ge 3$. In fact, if $\left|F^{\prime }\right|\le 2$, then $\delta \left(G-F^{\prime }\right)=0$. This implies ${\kappa }^1\left(G\right)=\min \left|F^{\prime }\right|\ge 3$. Therefore, ${\kappa }^1\left(G\right)=3$.

Case 2. $g=2$.

It is clear that $n\ne \mathrm{2,3,4}$ while $m=2$ and $n\ne \mathrm{3,4}$ while $m=3$. Now, we discuss by distinguishing three subcases.

Subcase 1. $2\le m\le 4$ and $n\ge 5$.

Let $F=\left\{w_{i3}\right\}$ for $1\le i\le m$. Notice that F is a cut set of G and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F\right)\right|\ge 2$ for every $v\in V\left(G\right)\backslash F$, we have ${\kappa }^2\left(G\right)\le \left|F\right|=m$ for $2\le m\le 4$. On the other hand, since ${\kappa }^1\left(G\right)\le {\kappa }^2\left(G\right)$ and ${\kappa }^1\left(G\right)=m$ for $m=2,3$, so we have ${\kappa }^2\left(G\right)\ge m$ for $m=2,3$. Thus ${\kappa }^2\left(G\right)=m$ for $m=2,3$.

Similarly, consider the case for $m=4$. Suppose $F^{\prime }\subset V\left(G\right)$ be a 2-good- neighbor cut of G, then $G-F^{\prime }$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F^{\prime }\right)\right|\ge 2$ for each $v\in \left(V\left(G\right)\backslash F^{\prime }\right)$. It is not difficult find that $\left|C\right|\ge 2$ and $\left|N\left(C\right)\right|\ge 4$ for every component of $G-F^{\prime }$. Thus ${\kappa }^2\left(G\right)\ge 4$. On the other hand, let $F_0=\left\{w_{13}\mathrm{,}{w}_{23}\mathrm{,}{w}_{31}\mathrm{,}{w}_{32}\right\}$. Clearly, $G-F_0$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F_0\right)\right|\ge 2$ for $v\in V\left(G\right)\backslash F_0$. So ${\kappa }^2\left(G\right)\le \left|F_0\right|=4$. And thus we get ${\kappa }^2\left(G\right)=4$ for $m=4$.

Subcase 2. $m=n=4$.

Let $F_0=\left\{w_{ij}\right\}$ for $i=1,2$, $j=3,4$ and $i=3,4$, $j=1,2$. It is clear that $G-F_0$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F_0\right)\right|\ge 2$ for every $v\in V\left(G\right)\backslash F_0$. Thus ${\kappa }^2\left(G\right)\le \left|F_0\right|=8$. On the other hand, suppose $F\subset V\left(G\right)$ is a 2-good- neighbor cut of G, then $G-F$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F\right)\right|\ge 2$ for $v\in V\left(G\right)\backslash F$. Then, we show $\left|F\right|\ge 8$. If not, assume $\left|F\right|\le 7$, then by the structure of G, there must be $v\in V\left(G\right)\backslash F$ such that $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F\right)\right|\le 1$, this contradicts to the choose of F. So ${\kappa }^2\left(G\right)\ge \left|F\right|\ge 8$ and thus ${\kappa }^2\left(G\right)=8$ for $m=n=4$.

Subcase 3. $n\ge m\ge 5$.

Let $F_0=\left\{w_{13}\mathrm{,}{w}_{23}\mathrm{,}{w}_{31}\mathrm{,}{w}_{32}\right\}$. It is clear that $G-F_0$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F_0\right)\right|\ge 2$ for every $v\in V\left(G\right)\backslash F_0$. Thus, we have ${\kappa }^2\left(G\right)\le \left|F_0\right|=4$. On the other hand, suppose $F\subset V\left(G\right)$ is a 2-good-neighbor cut of G, then $G-F$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F\right)\right|\ge 2$ for $v\in \left(V\left(G\right)\backslash F\right)$. Notice that each component C of $G-F$ is 2-connected and $\left|N\left(C\right)\right|\ge 4$. So ${\kappa }^2\left(G\right)\ge 4$ and then get ${\kappa }^2\left(G\right)=4$.

This completes the proof.

Example 2. The 2-good-neighbor connectivity of $P_5\times P_5$ is 4 with $F=\left\{w_{31}\mathrm{,}{w}_{32}\mathrm{,}{w}_{13}\mathrm{,}{w}_{23}\right\}$, which is shown in Figure 2.

Theorem 2.4. Let g, m and n be non-negative integers with $m\ge \mathrm{2,}n\ge 3$ . Then the g-good-neighbor connectivity of cylindrical grid $P_m\times C_n$ is

1)For $g=0$, ${\kappa }^g\left(P_m\times C_n\right)=\kappa \left(P_m\times C_n\right)=3$.

2) For $g=1$, ${\kappa }^g\left(P_m\times C_n\right)=(\begin{array}{ll}3,\hfill & n=3;\hfill \\ 4,\hfill & n\ge 4.\hfill \end{array}$

3) For $g=2$, ${\kappa }^g\left(P_m\times C_n\right)=(\begin{array}{ll}n,\hfill & 3\le n\le 5;\hfill \\ 4,\hfill & m=2,n\ge 6;\hfill \\ 6,\hfill & m\ge 3,n\ge 6.\hfill \end{array}$

4) For $g=3$, ${\kappa }^g\left(P_m\times C_n\right)=n$ for $m\ge 5$.

Proof. Similarly, let $P_m\times C_n=G$ with $V\left(P_m\right)=\left\{u_1,u_2,\cdots ,u_m\right\}$, $V\left(C_n\right)=\left\{v_1,v_2,\cdots ,v_n\right\}$. Then $V\left(G\right)=\left\{w_{ij}|w_{ij}=\left(u_i,v_j\right)|u_i\in V\left(P_m\right)\text{and}{v}_j\in V\left(C_n\right)\right\}$. Suppose F is a vertex cut set of G, consider the minimum degree of $G-F$ is not more than 4, so $g=0,1,2$ and 3. By $\kappa \left(G\right)=3$, we directly get ${\kappa }^0\left(G\right)=3$. Now we distinguish three cases to determine ${\kappa }^g\left(G\right)$ for $g=1,2,3$.

Case 1. $g=1$.

Subcase 1. $n=3$.

Consider $n=3$ and $g=1$, here $m\ge 3$. First, let $F_0=\left\{w_{13}\mathrm{,}{w}_{21}\mathrm{,}{w}_{22}\right\}$. It is clear that $G-F_0$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F_0\right)\right|\ge 1$ for every $v\in V\left(G\right)\backslash F_0$. Thus $k^1\left(G\right)\le 3$. On the other hand, by Lemma 2.1, we have ${\kappa }^1\left(G\right)\ge {\kappa }^0\left(G\right)=3$. So ${\kappa }^1\left(G\right)=3$ for $n=3$.

Subcase 2. $n\ge 4$.

Let $F_0=\left\{w_{13}\mathrm{,}{w}_{21}\mathrm{,}{w}_{1n}\mathrm{,}{w}_{22}\right\}$ for $n\ge 4$. It is clear that $G-F_0$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F_0\right)\right|\ge 1$ for every $v\in V\left(G\right)\backslash F_0$. Thus, we directly get

Figure 2. ${\kappa }^2\left(P_5\times P_5\right)=4$.

${\kappa }^1\left(G\right)\le 4$. On the other hand, suppose that $F\subset V\left(G\right)$ is a 1-good-neighbor cut of G, then $G-F$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F\right)\right|\ge 1$ for $v\in V\left(G\right)\backslash F$. By the structure of G, we find that there exists a component C of $G-F$ such that $\left|C\right|\ge 2$ and $\delta \left(C\right)=1$. Further, we find $\left|N\left(C\right)\right|\ge 4$ ${\kappa }^1\left(G\right)\ge 4$. Thus ${\kappa }^1\left(G\right)=4$.

Case 2. $g=2$.

Subcase 1. $3\le n\le 5$.

Consider $g=2$ and $3\le n\le 4$, here $m\ge 3$. First, let $F_0=\left\{w_{2j}\right\}$ for $1\le j\le n$. Clearly, $G-F_0$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F_0\right)\right|\ge 2$ for every $v\in V\left(G\right)\backslash F_0$. Thus ${\kappa }^2\left(G\right)\le \left|F_0\right|=n$ for $3\le n\le 5$. On the other hand, by ${\kappa }^1\left(G\right)\le {\kappa }^2\left(G\right)$ and ${\kappa }^1\left(G\right)=n$ for $n=3,4$, we have ${\kappa }^2\left(G\right)\ge n$ for $n=3,4$. Thus ${\kappa }^2\left(G\right)=n$ for $n=3,4$.

Now, consider the case for $n=5$ by Case 1, we directly get ${\kappa }^2\left(G\right)\ge {\kappa }^1\left(G\right)=4$. Further, we can show ${\kappa }^2\left(G\right)\ne 4$. If not, assume ${\kappa }^2\left(G\right)=4$, then there exists a 2-good neighbor cut set $F^{\prime }\subset V\left(G\right)$ with $\left|F^{\prime }\right|=4$ such that $G-F^{\prime }$ is disconnected. Combine this with the structure of G, there always exists a vertex $v\in \left(V\left(G\right)\backslash F^{\prime }\right)$ satisfies $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F^{\prime }\right)\right|\le 1$. This contradicts to the choose of $F^{\prime }$. Thus ${\kappa }^2\left(G\right)\ne 4$ and then ${\kappa }^2\left(G\right)\ge 5$. So ${\kappa }^2\left(G\right)=n$ for $n=5$.

Subcase 2. $m\ge 2$ and $n\ge 6$.

First, consider the case for $m=2$ and $n\ge 6$. Let $F_0=\left\{w_{i3}\mathrm{,}{w}_{in}\right\}$ for $1\le i\le m$. Clearly, $G-F_0$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F_0\right)\right|\ge 2$ for every $v\in V\left(G\right)\backslash F_0$. Thus, we have ${\kappa }^2\left(G\right)\le \left|F_0\right|=2m$. Notice that ${\kappa }^1\left(G\right)=4$, then ${\kappa }^2\left(G\right)\ge 4=2m$. So ${\kappa }^2\left(G\right)=2m$ for $m=2$.

Next, consider the case for $m\ge 3$ and $n\ge 6$. Let $F_1=\left\{w_{i3},w_{in}\right\}$ with $1\le i\le m$ for $m=3$ and $F_2=\left\{w_{13},w_{1n},w_{23},w_{2n},w_{31},w_{32}\right\}$ for $m>3$. It is clear that $G-F_1$ and $G-F_2$ are disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F_i\right)\right|\ge 2$ for every $v\in V\left(G\right)\backslash F_i$ for $i=1,2$. Thus, we have ${\kappa }^2\left(G\right)\le \left|F_i\right|=6$. On the other hand, suppose that $F\subset V\left(G\right)$ is a 2-good-neighbor cut of G, then $G-F$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F\right)\right|\ge 2$ for $v\in V\left(G\right)\backslash F$. This follows that each component C of $G-F$ satisfies $\left|C\right|\ge 4$ and thus $\left|N\left(C\right)\right|\ge 6$. So, we have ${\kappa }^2\left(G\right)\ge 6$ and thus ${\kappa }^2\left(G\right)=6$ while $m\ge 3$ and $n\ge 6$.

Case 3. $g=3$.

Suppose $F^{\prime }$ is a 3-good-neighbor cut of G, $g=3$ means component of $G-F^{\prime }$ is such as $P_k\times C_n$ for $k\ge 2$, so here consider $m\ge 5$. Notice that $w_{ij}\in F^{\prime }$ for all $1\le j\le n$, if $w_{ij}\in F^{\prime }$ for some j. Thus $\left|F^{\prime }\right|\ge n$ and ${\kappa }^3\left(G\right)\ge \left|F^{\prime }\right|\ge n$. On the other hand, let $F_0=\left\{w_{3j}\right\}$ for $1\le j\le n$. Clearly, $G-F_0$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F_0\right)\right|\ge 3$ for every $v\in V\left(G\right)\backslash F_0$. So we have ${\kappa }^3\left(G\right)\le n$. Therefore, we get ${\kappa }^3\left(G\right)=n$.

This completes the proof.

Example: The 3-good-neighbor connectivity of $P_5\times C_6$ is 6 with $F=\left\{w_{31}\mathrm{,}{w}_{32}\mathrm{,}{w}_{33}\mathrm{,}{w}_{34}\mathrm{,}{w}_{35}\mathrm{,}{w}_{36}\right\}$, which is shown in Figure 3.

Theorem 2.5 Let g, m and n be non-negative integers with $n\ge m\ge 3$ . Then the g-good-neighbor connectivity of torus $C_m\times C_n$ is

Figure 3. ${\kappa }^3\left(P_5\times C_6\right)=6$.

1) For $g=0$, ${\kappa }^g\left(C_m\times C_n\right)=4$.

2) For $g=1$, ${\kappa }^g\left(C_m\times C_n\right)=(\begin{array}{ll}5,\hfill & m=3;\hfill \\ 6,\hfill & m\ge 4.\hfill \end{array}$

3) For $g=2$, ${\kappa }^g\left(C_m\times C_n\right)=(\begin{array}{ll}2m,\hfill & 3\le m\le 4;\hfill \\ 8,\hfill & m\ge 5.\hfill \end{array}$

4) For $g=3$, ${\kappa }^g\left(C_m\times C_n\right)=2m$ for $n\ge 6$.

Proof. Let $C_m\times C_n=G$ and $V\left(C_m\right)=\left\{u_1,u_2,\cdots ,u_m\right\}$, $V\left(C_n\right)=\left\{v_1,v_2,\cdots ,v_n\right\}$. Then $V\left(G\right)=\left\{w_{ij}|w_{ij}=\left(u_i,v_j\right)|u_i\in V\left(C_m\right)\text{and}{v}_j\in V\left(C_n\right)\right\}$. Suppose that F is a vertex cut set of G, it is not difficult find the minimum degree of $G-F$ is not more than 4. So here, we only consider $g=0,1,2$ and 3. Notice that G is 4-regular, so we directly get ${\kappa }^0\left(G\right)=\kappa \left(G\right)=4$. Now, we distinguish three cases to determine ${\kappa }^g\left(G\right)$ by $g=1,2,3$.

Case 1. $g=1$.

Subcase 1. $m=3$.

Let $F_0=\left\{w_{12}\mathrm{,}{w}_{1n}\mathrm{,}{w}_{21}\mathrm{,}{w}_{32}\mathrm{,}{w}_{3n}\right\}$. It is clear that $G-F_0$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F_0\right)\right|\ge 1$ for every $v\in V\left(G\right)\backslash F_0$. So we have ${\kappa }^1\left(G\right)\le \left|F_0\right|=5$. On the other hand, it is clear that ${\kappa }^1\left(G\right)\ge {\kappa }^0\left(G\right)=4$. Further, we can show ${\kappa }^1\left(G\right)\ne 4$. If not, assume ${\kappa }^1\left(G\right)=4$, then there exists a 1-good-neighbor cut $F\subset V\left(G\right)$ with $\left|F\right|=4$ such that $G-F$ is disconnected. Notice that G is 4-regular, there always exists a vertex $v_0\in V\left(G\right)\backslash F$ such that $\left|N\left(v_0\right)\cap \left(V\left(G\right)\backslash F\right)\right|=0$. This contradicts to the choice of F. Thus, we get ${\kappa }^1\left(G\right)\ge 5$. So ${\kappa }^1\left(G\right)=5$.

Subcase 2. $m\ge 4$.

Let $F_0=\left\{w_{13}\mathrm{,}{w}_{1n}\mathrm{,}{w}_{21}\mathrm{,}{w}_{22}\mathrm{,}{w}_{m1}\mathrm{,}{w}_{m2}\right\}$. Then $G-F_0$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F_0\right)\right|\ge 1$ for every $v\in \left(V\left(G\right)\backslash F_0\right)$. Thus, we get ${\kappa }^1\left(G\right)\le \left|F_0\right|=6$. Now, we show ${\kappa }^1\left(G\right)\ge 6$. Suppose $F\subset V\left(G\right)$ is a 1-good- neighbor cut of G, then $G-F$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F\right)\right|\ge 1$ for $v\in \left(V\left(G\right)\backslash F\right)$. Thus, there exist a component C with $\left|C\right|\ge 2$ such that $\delta \left(C\right)=1$. Notice that each pair nonadjacent vertices of G has at most two common neighbor vertices and two adjacent vertices of G has no common neighbor vertices in G, then we get $N\left(C\right)\ge 6$. This means $\left|F^{\prime }\right|\ge 6$. So, we get ${\kappa }^1\left(G\right)\ge 6$.

Case 2. $g=2$.

Subcase 1. $3\le m\le 4$.

Consider $g=2$, so here $n\ge 4$. Let $F_0=\left\{w_{ij}\right\}$ for $j=2,n$ and $1\le i\le m$. Clearly, $G-F_0$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F_0\right)\right|\ge 2$ for every $v\in V\left(G\right)\backslash F_0$. Thus ${\kappa }^2\left(G\right)\le \left|F_0\right|=2m$ while $3\le m\le 4$. On the other hand, suppose $F\subset V\left(G\right)$ is a 2-good-neighbor cut of G, then $G-F$ has a component C with $\left|C\right|\ge 4$ and $\delta \left(C\right)=2$. Notice that G is 4-regular and each pair nonadjacent vertices has at most two common neighbor vertices and two adjacent vertices has no common neighbor vertices in G, it follows that $\left|N\left(C\right)\right|\ge 2m$ for $3\le m\le 4$. This means $\left|F\right|\ge 2m$ and we get ${\kappa }^2\left(G\right)\ge 2m$. Thus ${\kappa }^2\left(G\right)=2m$ for $3\le m\le 4$.

Subcase 2. $m\ge 5$.

Let $F_0=\left\{w_{ij}\right\}$ for $i=3,m$ while $j=1,2$ and $i=1,2$ while $j=3,n$. It is clear that $G-F_0$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F_0\right)\right|\ge 2$ for every $v\in V\left(G\right)\backslash F_0$. So we get ${\kappa }^2\left(G\right)\le 8$. On the other hand, suppose $F\subset V\left(G\right)$ is a 2-good-neighbor cut of G, then $G-F$ has a component C with $\left|C\right|\ge 4$ and $\delta \left(C\right)=2$. Consider G is 4-regular, we similarly get $\left|N\left(C\right)\right|\ge 8$. Thus ${\kappa }^2\left(G\right)\ge 8$. So, we get ${\kappa }^2\left(G\right)=8$.

Case 3. $g=3$.

Consider $g=3$, so here $n\ge 6$. Let $F_0=\left\{w_{ij}\right\}$ for $j=3,n$ and $1\le i\le m$. Then $G-F_0$ is disconnected and $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F_0\right)\right|\ge 3$ for every

$v\in V\left(G\right)\backslash F_0$. So, we have ${\kappa }^3\left(G\right)\le \left|F_0\right|=2m$ for $n\ge 6$. On the other hand, if $3\le m\le 4$, by Lemma 2.1, we have ${\kappa }^3\left(G\right)\ge {\kappa }^2\left(G\right)=2m$. Thus ${\kappa }^3\left(G\right)=2m$

Figure 4. ${\kappa }^3\left(C_6\times C_6\right)=12$.

for $3\le m\le 4$. If $m\ge 5$, suppose F is a 3-good-neighbor cut of G, it is not difficult find that $w_{ij}\in F$ for all i if $w_{ij}\in F$ for some i and j. Combine this with $\left|N\left(v\right)\cap \left(V\left(G\right)\backslash F\right)\right|\ge 3$ for every $v\in V\left(G\right)\backslash F$, we have $\left|F\right|\ge 2m$ and ${\kappa }^3\left(G\right)\ge 2m$. So, we get ${\kappa }^3\left(G\right)=2m$.

This completes the proof.

Example: The 3-good-neighbor connectivity of $C_6\times C_6$ is 12 with $F=\left\{w_{31}\mathrm{,}{w}_{32}\mathrm{,}{w}_{33}\mathrm{,}{w}_{34}\mathrm{,}{w}_{35}\mathrm{,}{w}_{36}\mathrm{,}{w}_{61}\mathrm{,}{w}_{62}\mathrm{,}{w}_{63}\mathrm{,}{w}_{64}\mathrm{,}{w}_{65}\mathrm{,}{w}_{66}\right\}$, which is shown in Figure 4.

3. Concluding Remark

In this paper, we focus our attention on the g-good neighbor connectivity of some Cartesian product graphs. We have determined the g-good-neighbor connectivity of the Cartesian product of two complete graphs $K_m$ and $K_n$ for

$0\le g\le \lfloor \frac{m+n-4}{2}\rfloor$, mesh $P_m\times P_n$ for $0\le g\le 2$, cylindrical grid $P_m\times C_n$ and

torus $C_m\times C_n$ for $0\le g\le 3$. But the g-good neighbor connectivity of the Cartesian product for the general graphs is still unknown, even for the bounds. In the future, we will devote ourselves to this research.

Acknowledgements

The authors would like to thank anonymous reviewers for their valuable comments and suggestions to improve the quality of the article. This work was supported by QHAFC No. 2022-ZJ-753.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Fàbrega, J. and Fiol, M.A. (1996) On the Extra Connectivity of Graphs. Discrete Mathematics, 155, 49-57. https://doi.org/10.1016/0012-365X(94)00369-T
[2]	Peng, S.-L., Lin, C.-K., Tan, J.J.M. and Hsu, L.-H. (2012) The g-Good-Neighbor Conditional Diagnosability of Hypercube under PMC Model. Applied Mathematics and Computation, 218, 10406-10412. https://doi.org/10.1016/j.amc.2012.03.092
[3]	Wang, S.Y., Wang, Z.H. and Wang, M.J.S. (2017) The 2-Good-Neighbor Connectivity and 2-Good-Neighbor Diagnosability of Bubble-Sort Star Graph Networks. Discrete Applied Mathematics, 217, 691-706. https://doi.org/10.1016/j.dam.2016.09.047
[4]	Ren, Y.X. and Wang, S.Y. (2017) The 1-Good-Neighbor Connectivity and Diagnosability of Locally Twisted Cubes. Chinese Quarterly Journal of Mathematics, 32, 371-381.
[5]	Ren, Y.X. and Wang, S.Y. (2017) The g-Good-Neighbor Diagnosability of Locally Twisted Cubes. Theoretical Computer Science, 697, 91-97. https://doi.org/10.1016/j.tcs.2017.07.030
[6]	Wei, Y.L. and Xu, M. (2018) The 1,2-Good-Neighbor Conditional Diagnosabilities of Regular Graphs. Applied Mathematics and Computation, 334, 295-310. https://doi.org/10.1016/j.amc.2018.04.014
[7]	Wang, S.Y. and Wang, M.J.S. (2019) The g-Good-Neighbor and g-Extra Diagnosability of Networks. Theoretical Computer Science, 773, 107-114. https://doi.org/10.1016/j.tcs.2018.09.002
[8]	El-Mesady, A. and Bazighifan, O. (2022) Construction of Mutually Orthogonal Graph Squares Using Novel Product Techniques. Journal of Mathematics, 2022, Article ID: 9722983. https://doi.org/10.1155/2022/9722983
[9]	El-Mesady, A. and Shaaban, S.M. (2021) Generalization of MacNeish’s Kronecker Product Theorem of Mutually Orthogonal Latin Squares. AKCE International Journal of Graphs and Combinatorics, 18, 117-122. https://doi.org/10.1080/09728600.2021.1966349
[10]	El-Mesady, A., Bazighifan, O. and Al-Mdallal, Q. (2022) On Infinite Circulant-Balanced Complete Multipartite Graphs Decompositions Based on Generalized Algorithmic Approaches. Alexandria Engineering Journal, 61, 11267-11275. https://doi.org/10.1016/j.aej.2022.04.022
[11]	El-Shanawany, R., Higazy, M. and El-Mesady, A. (2013) On Cartesian Products of Orthogonal Double Covers. International Journal of Mathematics and Mathematical Sciences, 2013, Article ID: 265136. https://doi.org/10.1155/2013/265136
[12]	El-Mesady, A., Farahat, T. and El-Shanawany, R. (2021) Construction of the Enormous Complete Bipartite Graphs and Orthogonal Double Covers Based on the Cartesian Product. 2021 International Conference on Electronic Engineering (ICEEM), Menouf, 3-4 July 2021, 1-4. https://doi.org/10.1109/ICEEM52022.2021.9480620
[13]	El-Shanawany, R.A., Higazy, M. and Shabana, H. (2015) Cartesian Product of Two Symmetric Starter Vectors of Orthogonal Double Covers. AKCE International Journal of Graphs and Combinatorics, 12, 59-63. https://doi.org/10.1016/j.akcej.2015.06.009
[14]	Wang, Z., Mao, Y.P., Hsieh, S.-Y. and Wu, J.C. (2019) On the g-Good-Neighbor Connectivity of Graphs. Theoretical Computer Science, 804, 139-148. https://doi.org/10.1016/j.tcs.2019.11.021