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

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 .

Share and Cite:

Li, Y. , Xie, T. and Qin, X. (2023) The g-Good-Neighbor Connectivity of Some Cartesian Product Graphs. Open Journal of Discrete Mathematics, 13, 27-37. doi: 10.4236/ojdm.2023.131003.

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 = ( V , E ) be a given connected graph with vertices set V ( G ) and edges set E ( G ) . 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 V , we by N ( v ) denote the set of neighbors of v and by N ( S ) denote the set of neighbors of every vertex in S. A set F V is called a g-good-neighbor faulty set of G if | N ( v ) ( V \ F ) | 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 κ g ( G ) . Clearly, κ 0 ( G ) = κ ( G ) 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 BSn is 8 n 22 for n 5 and the 2-good-neighbor connectivity of BS4 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 8 n 24 for n 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 × G 2 whose vertex set is the Cartesian product of the sets V ( G 1 ) and V ( G 2 ) . Two vertices ( u 1 , v 1 ) and ( u 2 , v 2 ) are adjacent in G 1 × G 2 precisely when either u 1 = u 2 and v 1 v 2 E ( G 2 ) or v 1 = v 2 and u 1 u 2 E ( G 1 ) . 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 g m + n 4 2 , mesh

P m × P n for 0 g 2 , cylindrical grid P m × C n and torus C m × C n for 0 g 3 . As usual, we by Δ ( G ) and κ ( G ) 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 κ g ( G ) κ g + 1 ( G ) .

Theorem 2.2. Let K m × K n be Cartesian product of complete graph K m and

K n with 1 m n and g be non-negative integer with 0 g m + n 4 2 . Then the g-good-neighbor connectivity of K m × K n is

1) For g = 0 , κ g ( K m × K n ) = κ ( K m × K n ) = m + n 2 .

2)For 1 g m + n 4 2 ,

κ g ( K m × K n ) = ( m ( g + 2 ) ( m + 2 g + 4 n ) 2 8 , n 2 g + 8 3 m ; ( m 1 ) ( m 2 g 6 + n ) + m ( g + 2 ) , n < 2 g + 8 3 m .

Proof. Let G = K m × K n with V ( G ) = { w i j | w i j = ( u i , v j ) | u i V ( K m ) , v j V ( K n ) } for 1 i m and 1 j n . Consider G is m + n 2 regular, thus, we have κ 0 ( G ) = κ ( G ) = m + n 2 . Suppose F is a g-good neighbor cut set of G with minimum cardinality and let G F = G 1 G 2 G p .

Now, we further show that G k = K m k × K n k with m k n k for k = 1 , 2 , , p . In fact, it is enough if we show that whenever ( u i , v r ) , ( u i , v s ) , ( u j , v r ) V ( G k ) , then ( u j , v s ) V ( G k ) . On the contrary, if ( u j , v s ) V ( G G k ) , then we by the definition of K m × K n get ( u j , v s ) F . Let F = F ( u j , v s ) , then ( u j , v s ) is adjacent with ( u i , v s ) , ( u j , v r ) in G F and [ G k { ( u j , v s ) } ] is a component of G F such that | N ( v ) ( V ( G ) \ F ) | g for every v V ( G ) \ F . This implies F is also a g-good neighbor cut set of G with | F | = | F | 1 . This contradicts to the fact F is of minimum cardinality. So, we have G k = K m k × K n k with m k n k for k = 1 , 2 , , p . Further, we by the minimality of F know that G F has exactly two components. This means G F = ( K m 1 × K n 1 ) ( K m 2 × K n 2 ) .

Notice that F is a g-good neighbor cut set of G, we have m 1 + n 1 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 2 ( g + 2 ) , then g m + n 2 2 . Thus, we have

| F | = min { m 1 n 2 + m 2 n 1 } = min { ( m m 2 ) n 2 + m 2 ( n n 2 ) } = min { ( m 2 m 2 ) ( g + 2 m 2 ) + n m 2 } = min { 2 m 2 2 ( m + 2 g + 4 n ) m 2 + m ( g + 2 ) } .

Notice that 2 n 1 m 1 + n 1 g + 2 , we have n 1 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 ( g + 2 ) . So m 1 m + n 3 ( g + 2 ) 2 . Thus 3 ( g + 2 ) 2 n m 2 m 1 .

Now, let f ( x ) = 2 x 2 ( m + 2 g + 4 n ) x + m ( g + 2 ) , the following we determine the minimum value of f ( x ) in interval [ 3 ( g + 2 ) 2 n , m 1 ] .

By 2 n m + n 2 ( g + 2 ) , we have n g + 2 . Thus

m + 2 g + 4 n 4 ( 3 ( g + 2 ) 2 n ) = m n 4 + n g 2 0 . By comparing the difference between m + 2 g + 4 n 4 and m 1 , we discuss the minimum value of f ( x ) .

If n > 2 g + 8 3 m , let m + 2 g + 4 n = t , then min f ( x ) = f ( m + 2 g + 4 n 4 ) = f ( t 4 ) = 2 ( t 4 ) 2 t 2 4 + m ( g + 2 ) = m ( g + 2 ) t 2 8 ;

If n 2 g + 8 3 m , then min f ( x ) = f ( m 1 ) = 2 ( m 1 ) 2 ( m + 2 g + 4 n ) ( m 1 ) + m ( g + 2 ) = ( m 1 ) ( m 2 g 6 + n ) + m ( g + 2 ) .

By the above analysis, we get

κ g ( K m × K n ) = | F | = ( m ( g + 2 ) ( m + 2 g + 4 n ) 2 8 , n > 2 g + 8 3 m ; ( m 1 ) ( m 2 g 6 + n ) + m ( g + 2 ) , n 2 g + 8 3 m .

This completes the proof.

Example 1. The 1-good-neighbor connectivity of K 3 × K 4 is 6 with F = { w 12 , w 13 , w 21 , w 24 , w 31 , w 34 } , which is shown in Figure 1.

Theorem 2.3. Let g, m and n be non-negative integers with n m 2 . Then the g-good-neighbor connectivity of mesh P m × P n is

1) For g = 0 , κ g ( P m × P n ) = κ ( P m × P n ) = 2 .

2) For g = 1 , κ g ( P m × P n ) = ( 2 , m = 2 ; 3 , m 3.

3)For g = 2 , κ g ( P m × P n ) = ( m , 2 m 4 , n 5 ; 8 , m = n = 4 ; 4 , m , n 5.

Proof. Let P m × P n = G with V ( P m ) = { u 1 , u 2 , , u m } and V ( P n ) = { v 1 , v 2 , , v n } . Then V ( G ) = { w i j | w i j = ( u i , v j ) | u i V ( P m ) and v j V ( P n ) } . 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 κ ( G ) = 2 we have κ 0 ( G ) = 2 . The following we by distinguishing cases to determine κ g ( G ) .

Figure 1. κ 1 ( K 3 × K 4 ) = 6 .

Case 1. g = 1 .

g = 1 means n 2 , so n 3 .

Subcase 1. m = 2 .

By Lemma 2.1, we have κ 1 ( G ) κ 0 ( G ) = 2 . On the other hand, let F = { w 1 j , w 2 j } for j = 2 or n 1 . It is clear that G F is disconnected and | N ( v ) ( V ( G ) \ F ) | 1 for every v V ( G ) \ F . By the definition of g-good- neighbor connectivity, we have κ 1 ( G ) | F | = 2 . Therefore, we get κ 1 ( G ) = 2 .

Subcase 2. m 3 .

First, let F = { w 12 , w 22 , w 31 } . Clearly, G F is disconnected and | N ( v ) ( V ( G ) \ F ) | 1 for every v G F , so we have κ 1 ( G ) | F | = 3 . On the other hand, suppose F V ( G ) is a vertex cut set of G such that | N ( v ) ( V ( G ) \ F ) | 1 for every v V ( G ) \ F . Then G F has a component C with | C | 2 and the minimum degree of C is δ ( C ) = 1 . Further, we have | F | 3 . In fact, if | F | 2 , then δ ( G F ) = 0 . This implies κ 1 ( G ) = min | F | 3 . Therefore, κ 1 ( G ) = 3 .

Case 2. g = 2 .

It is clear that n 2,3,4 while m = 2 and n 3,4 while m = 3 . Now, we discuss by distinguishing three subcases.

Subcase 1. 2 m 4 and n 5 .

Let F = { w i 3 } for 1 i m . Notice that F is a cut set of G and | N ( v ) ( V ( G ) \ F ) | 2 for every v V ( G ) \ F , we have κ 2 ( G ) | F | = m for 2 m 4 . On the other hand, since κ 1 ( G ) κ 2 ( G ) and κ 1 ( G ) = m for m = 2 , 3 , so we have κ 2 ( G ) m for m = 2 , 3 . Thus κ 2 ( G ) = m for m = 2 , 3 .

Similarly, consider the case for m = 4 . Suppose F V ( G ) be a 2-good- neighbor cut of G, then G F is disconnected and | N ( v ) ( V ( G ) \ F ) | 2 for each v ( V ( G ) \ F ) . It is not difficult find that | C | 2 and | N ( C ) | 4 for every component of G F . Thus κ 2 ( G ) 4 . On the other hand, let F 0 = { w 13 , w 23 , w 31 , w 32 } . Clearly, G F 0 is disconnected and | N ( v ) ( V ( G ) \ F 0 ) | 2 for v V ( G ) \ F 0 . So κ 2 ( G ) | F 0 | = 4 . And thus we get κ 2 ( G ) = 4 for m = 4 .

Subcase 2. m = n = 4 .

Let F 0 = { w i j } for i = 1 , 2 , j = 3 , 4 and i = 3 , 4 , j = 1 , 2 . It is clear that G F 0 is disconnected and | N ( v ) ( V ( G ) \ F 0 ) | 2 for every v V ( G ) \ F 0 . Thus κ 2 ( G ) | F 0 | = 8 . On the other hand, suppose F V ( G ) is a 2-good- neighbor cut of G, then G F is disconnected and | N ( v ) ( V ( G ) \ F ) | 2 for v V ( G ) \ F . Then, we show | F | 8 . If not, assume | F | 7 , then by the structure of G, there must be v V ( G ) \ F such that | N ( v ) ( V ( G ) \ F ) | 1 , this contradicts to the choose of F. So κ 2 ( G ) | F | 8 and thus κ 2 ( G ) = 8 for m = n = 4 .

Subcase 3. n m 5 .

Let F 0 = { w 13 , w 23 , w 31 , w 32 } . It is clear that G F 0 is disconnected and | N ( v ) ( V ( G ) \ F 0 ) | 2 for every v V ( G ) \ F 0 . Thus, we have κ 2 ( G ) | F 0 | = 4 . On the other hand, suppose F V ( G ) is a 2-good-neighbor cut of G, then G F is disconnected and | N ( v ) ( V ( G ) \ F ) | 2 for v ( V ( G ) \ F ) . Notice that each component C of G F is 2-connected and | N ( C ) | 4 . So κ 2 ( G ) 4 and then get κ 2 ( G ) = 4 .

This completes the proof.

Example 2. The 2-good-neighbor connectivity of P 5 × P 5 is 4 with F = { w 31 , w 32 , w 13 , w 23 } , which is shown in Figure 2.

Theorem 2.4. Let g, m and n be non-negative integers with m 2, n 3 . Then the g-good-neighbor connectivity of cylindrical grid P m × C n is

1)For g = 0 , κ g ( P m × C n ) = κ ( P m × C n ) = 3 .

2) For g = 1 , κ g ( P m × C n ) = ( 3 , n = 3 ; 4 , n 4.

3) For g = 2 , κ g ( P m × C n ) = ( n , 3 n 5 ; 4 , m = 2 , n 6 ; 6 , m 3 , n 6.

4) For g = 3 , κ g ( P m × C n ) = n for m 5 .

Proof. Similarly, let P m × C n = G with V ( P m ) = { u 1 , u 2 , , u m } , V ( C n ) = { v 1 , v 2 , , v n } . Then V ( G ) = { w i j | w i j = ( u i , v j ) | u i V ( P m ) and v j V ( C n ) } . 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 κ ( G ) = 3 , we directly get κ 0 ( G ) = 3 . Now we distinguish three cases to determine κ g ( G ) for g = 1 , 2 , 3 .

Case 1. g = 1 .

Subcase 1. n = 3 .

Consider n = 3 and g = 1 , here m 3 . First, let F 0 = { w 13 , w 21 , w 22 } . It is clear that G F 0 is disconnected and | N ( v ) ( V ( G ) \ F 0 ) | 1 for every v V ( G ) \ F 0 . Thus k 1 ( G ) 3 . On the other hand, by Lemma 2.1, we have κ 1 ( G ) κ 0 ( G ) = 3 . So κ 1 ( G ) = 3 for n = 3 .

Subcase 2. n 4 .

Let F 0 = { w 13 , w 21 , w 1 n , w 22 } for n 4 . It is clear that G F 0 is disconnected and | N ( v ) ( V ( G ) \ F 0 ) | 1 for every v V ( G ) \ F 0 . Thus, we directly get

Figure 2. κ 2 ( P 5 × P 5 ) = 4 .

κ 1 ( G ) 4 . On the other hand, suppose that F V ( G ) is a 1-good-neighbor cut of G, then G F is disconnected and | N ( v ) ( V ( G ) \ F ) | 1 for v V ( G ) \ F . By the structure of G, we find that there exists a component C of G F such that | C | 2 and δ ( C ) = 1 . Further, we find | N ( C ) | 4 κ 1 ( G ) 4 . Thus κ 1 ( G ) = 4 .

Case 2. g = 2 .

Subcase 1. 3 n 5 .

Consider g = 2 and 3 n 4 , here m 3 . First, let F 0 = { w 2 j } for 1 j n . Clearly, G F 0 is disconnected and | N ( v ) ( V ( G ) \ F 0 ) | 2 for every v V ( G ) \ F 0 . Thus κ 2 ( G ) | F 0 | = n for 3 n 5 . On the other hand, by κ 1 ( G ) κ 2 ( G ) and κ 1 ( G ) = n for n = 3 , 4 , we have κ 2 ( G ) n for n = 3 , 4 . Thus κ 2 ( G ) = n for n = 3 , 4 .

Now, consider the case for n = 5 by Case 1, we directly get κ 2 ( G ) κ 1 ( G ) = 4 . Further, we can show κ 2 ( G ) 4 . If not, assume κ 2 ( G ) = 4 , then there exists a 2-good neighbor cut set F V ( G ) with | F | = 4 such that G F is disconnected. Combine this with the structure of G, there always exists a vertex v ( V ( G ) \ F ) satisfies | N ( v ) ( V ( G ) \ F ) | 1 . This contradicts to the choose of F . Thus κ 2 ( G ) 4 and then κ 2 ( G ) 5 . So κ 2 ( G ) = n for n = 5 .

Subcase 2. m 2 and n 6 .

First, consider the case for m = 2 and n 6 . Let F 0 = { w i 3 , w i n } for 1 i m . Clearly, G F 0 is disconnected and | N ( v ) ( V ( G ) \ F 0 ) | 2 for every v V ( G ) \ F 0 . Thus, we have κ 2 ( G ) | F 0 | = 2 m . Notice that κ 1 ( G ) = 4 , then κ 2 ( G ) 4 = 2 m . So κ 2 ( G ) = 2 m for m = 2 .

Next, consider the case for m 3 and n 6 . Let F 1 = { w i 3 , w i n } with 1 i m for m = 3 and F 2 = { w 13 , w 1 n , w 23 , w 2 n , w 31 , w 32 } for m > 3 . It is clear that G F 1 and G F 2 are disconnected and | N ( v ) ( V ( G ) \ F i ) | 2 for every v V ( G ) \ F i for i = 1 , 2 . Thus, we have κ 2 ( G ) | F i | = 6 . On the other hand, suppose that F V ( G ) is a 2-good-neighbor cut of G, then G F is disconnected and | N ( v ) ( V ( G ) \ F ) | 2 for v V ( G ) \ F . This follows that each component C of G F satisfies | C | 4 and thus | N ( C ) | 6 . So, we have κ 2 ( G ) 6 and thus κ 2 ( G ) = 6 while m 3 and n 6 .

Case 3. g = 3 .

Suppose F is a 3-good-neighbor cut of G, g = 3 means component of G F is such as P k × C n for k 2 , so here consider m 5 . Notice that w i j F for all 1 j n , if w i j F for some j. Thus | F | n and κ 3 ( G ) | F | n . On the other hand, let F 0 = { w 3 j } for 1 j n . Clearly, G F 0 is disconnected and | N ( v ) ( V ( G ) \ F 0 ) | 3 for every v V ( G ) \ F 0 . So we have κ 3 ( G ) n . Therefore, we get κ 3 ( G ) = n .

This completes the proof.

Example: The 3-good-neighbor connectivity of P 5 × C 6 is 6 with F = { w 31 , w 32 , w 33 , w 34 , w 35 , w 36 } , which is shown in Figure 3.

Theorem 2.5 Let g, m and n be non-negative integers with n m 3 . Then the g-good-neighbor connectivity of torus C m × C n is

Figure 3. κ 3 ( P 5 × C 6 ) = 6 .

1) For g = 0 , κ g ( C m × C n ) = 4 .

2) For g = 1 , κ g ( C m × C n ) = ( 5 , m = 3 ; 6 , m 4.

3) For g = 2 , κ g ( C m × C n ) = ( 2 m , 3 m 4 ; 8 , m 5.

4) For g = 3 , κ g ( C m × C n ) = 2 m for n 6 .

Proof. Let C m × C n = G and V ( C m ) = { u 1 , u 2 , , u m } , V ( C n ) = { v 1 , v 2 , , v n } . Then V ( G ) = { w i j | w i j = ( u i , v j ) | u i V ( C m ) and v j V ( C n ) } . 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 κ 0 ( G ) = κ ( G ) = 4 . Now, we distinguish three cases to determine κ g ( G ) by g = 1 , 2 , 3 .

Case 1. g = 1 .

Subcase 1. m = 3 .

Let F 0 = { w 12 , w 1 n , w 21 , w 32 , w 3 n } . It is clear that G F 0 is disconnected and | N ( v ) ( V ( G ) \ F 0 ) | 1 for every v V ( G ) \ F 0 . So we have κ 1 ( G ) | F 0 | = 5 . On the other hand, it is clear that κ 1 ( G ) κ 0 ( G ) = 4 . Further, we can show κ 1 ( G ) 4 . If not, assume κ 1 ( G ) = 4 , then there exists a 1-good-neighbor cut F V ( G ) with | F | = 4 such that G F is disconnected. Notice that G is 4-regular, there always exists a vertex v 0 V ( G ) \ F such that | N ( v 0 ) ( V ( G ) \ F ) | = 0 . This contradicts to the choice of F. Thus, we get κ 1 ( G ) 5 . So κ 1 ( G ) = 5 .

Subcase 2. m 4 .

Let F 0 = { w 13 , w 1 n , w 21 , w 22 , w m 1 , w m 2 } . Then G F 0 is disconnected and | N ( v ) ( V ( G ) \ F 0 ) | 1 for every v ( V ( G ) \ F 0 ) . Thus, we get κ 1 ( G ) | F 0 | = 6 . Now, we show κ 1 ( G ) 6 . Suppose F V ( G ) is a 1-good- neighbor cut of G, then G F is disconnected and | N ( v ) ( V ( G ) \ F ) | 1 for v ( V ( G ) \ F ) . Thus, there exist a component C with | C | 2 such that δ ( C ) = 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 ( C ) 6 . This means | F | 6 . So, we get κ 1 ( G ) 6 .

Case 2. g = 2 .

Subcase 1. 3 m 4 .

Consider g = 2 , so here n 4 . Let F 0 = { w i j } for j = 2 , n and 1 i m . Clearly, G F 0 is disconnected and | N ( v ) ( V ( G ) \ F 0 ) | 2 for every v V ( G ) \ F 0 . Thus κ 2 ( G ) | F 0 | = 2 m while 3 m 4 . On the other hand, suppose F V ( G ) is a 2-good-neighbor cut of G, then G F has a component C with | C | 4 and δ ( C ) = 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 | N ( C ) | 2 m for 3 m 4 . This means | F | 2 m and we get κ 2 ( G ) 2 m . Thus κ 2 ( G ) = 2 m for 3 m 4 .

Subcase 2. m 5 .

Let F 0 = { w i j } 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 | N ( v ) ( V ( G ) \ F 0 ) | 2 for every v V ( G ) \ F 0 . So we get κ 2 ( G ) 8 . On the other hand, suppose F V ( G ) is a 2-good-neighbor cut of G, then G F has a component C with | C | 4 and δ ( C ) = 2 . Consider G is 4-regular, we similarly get | N ( C ) | 8 . Thus κ 2 ( G ) 8 . So, we get κ 2 ( G ) = 8 .

Case 3. g = 3 .

Consider g = 3 , so here n 6 . Let F 0 = { w i j } for j = 3 , n and 1 i m . Then G F 0 is disconnected and | N ( v ) ( V ( G ) \ F 0 ) | 3 for every

v V ( G ) \ F 0 . So, we have κ 3 ( G ) | F 0 | = 2 m for n 6 . On the other hand, if 3 m 4 , by Lemma 2.1, we have κ 3 ( G ) κ 2 ( G ) = 2 m . Thus κ 3 ( G ) = 2 m

Figure 4. κ 3 ( C 6 × C 6 ) = 12 .

for 3 m 4 . If m 5 , suppose F is a 3-good-neighbor cut of G, it is not difficult find that w i j F for all i if w i j F for some i and j. Combine this with | N ( v ) ( V ( G ) \ F ) | 3 for every v V ( G ) \ F , we have | F | 2 m and κ 3 ( G ) 2 m . So, we get κ 3 ( G ) = 2 m .

This completes the proof.

Example: The 3-good-neighbor connectivity of C 6 × C 6 is 12 with F = { w 31 , w 32 , w 33 , w 34 , w 35 , w 36 , w 61 , w 62 , w 63 , w 64 , w 65 , w 66 } , 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 g m + n 4 2 , mesh P m × P n for 0 g 2 , cylindrical grid P m × C n and

torus C m × C n for 0 g 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

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.