On primality of Cartesian product of graphs

Abstract

Purpose

The present work focuses on the primality and the Cartesian product of graphs.

Design/methodology/approach

Given a graph G, a subset M of V (G) is a module of G if, for a, b ∈ M and x ∈ V (G) \ M, xa ∈ E(G) if and only if xb ∈ E(G). A graph G with at least three vertices is prime if the empty set, the single-vertex sets and V (G) are the only modules of G.

Findings

Motivated by works obtained on “the Cartesian product of graphs” and “the primality,” this paper creates a link between the two notions.

Originality/value

In fact, we study the primality of the Cartesian product of two connected graphs minus k vertices, where k ∈ {0, 1, 2}.

Citation

El Amri, N., Boudabbous, I. and Yaich, M. (2024), "On primality of Cartesian product of graphs", Arab Journal of Mathematical Sciences, Vol. ahead-of-print No. ahead-of-print. https://doi.org/10.1108/AJMS-09-2023-0023

1. Introduction

In our paper, G = (V, E) always denotes a finite undirected graph where V = V(G) is a non-empty and finite set, called the vertex-set of G and E = E(G) is a set of pairs of distinct vertices called the edge-set of G. An edge {u, v} of G is denoted by uv. Two distinct vertices u and v of G are adjacent whenever uv ∈ E; otherwise u and v are said to be non-adjacent. Given a finite and non-empty set V, (V, ∅) is the empty graph on V, whereas (V, [V]²) is the complete graph where [V]² is the set of pairs of V. The complement of each graph G = (V, E) is the graph G¯=(V,E¯) such that, for x ≠ y ∈ V, xy∈E¯ if and only if xy ∉ E. Any graph with just one vertex is referred to as trivial.

Let G = (V, E) be a graph and x be a vertex of G. A neighbor of x is vertex y of G such that xy ∈ E. The family of neighbors of x is called the neighborhood of x denoted by N_G(v). The vertex x is said to be pendant if it has a unique neighbor.

The degree of x, denoted by d_G(x), is to the number of its neighbors. For example, a vertex with degree zero is called an isolated vertex. The minimum vertex degree, known as the minimum degree of G is the smallest vertex degree of G denoted by δ(G).

The notation u— v signifies that uv ∈ E while u.…v means that uv ∉ E. For any two disjoint subsets I and J of V, I— J (resp. I.… J) signifies for each (x, y) ∈ I × J, x— y (resp. x.… y). In particular whenever I = {x}, we denote x— J (resp. x.…J). Furthermore, x ∼ J means x— J or x.…J. The negation is denoted by x ≁ J.

Let G = (V, E) be a graph. A graph G′ = (V′, E′) is a subgraph of G if V′ ⊆ V and E′ ⊆ E. Given a non-empty vertex subset X of V, the subgraph of G induced by X is the subgraph G[X] = (X, E ∩ [X]²). If X is a proper subset of V, G[V \ X] is also denoted by G − X and by G − x whenever X = {x}.

Let G = (V, E) and H = (V′, E′) be two graphs. A bijection f from V onto V′ is an isomorphism from G onto H provided that, for x ≠ y ∈ V, xy ∈ E if and only if f(x)f(y) ∈ E′.

Given a graph G = (V, E), a subset M of V is a module [1] (or a clan [2,3] or an interval [4,5]) of G provided that, for all a, b ∈ M and x ∈ V \ M, xa ∈ E if and only if xb ∈ E. Thus, M is a module of G if for all x ∈ V \ M, x ∼ M. For example, the empty set, V and {x} where x ∈ V are modules of G called trivial modules. A two-element module of G is known as a duo [6]. The graphs that have no duo, are called duo-free graphs. A graph is indecomposable [5] if all its modules are trivial. An indecomposable graph with at least three vertices is a prime graph [7]. All graphs with two vertices at most are indecomposable. However, all the 3-vertex graphs are not prime. Notice that the graphs G and G¯ share the same modules. Thus, G is prime if and only if G¯ is prime. Given n ≥ 2, the n-vertex graph denoted by P_n is defined on {1, …, n} as follows: for i, j ∈ {1, …, n}, ij is an edge of P_n if |i − j| = 1. Each graph that is isomorphic to P_n is called a path. It is clear that a path with at least 4 vertices is a prime graph. A path with extremities x and y is denoted by (x, y)-path.

Let G = (V, E) be a prime graph. A vertex x of G is critical if G − x is not prime. The graph G is critical if all its vertices are critical. The indecomposability graph of the graph G, denoted by I(G), is the graph defined on the set V(G) as follows: for u ≠ v ∈ V(G), uv is an edge of I(G) if G − {u, v} is prime.

Given a graph G = (V, E), a non-empty subset C of V is a connected component of G if for x ∈ C and y ∈ V \ C, xy ∉ E and if, for x ≠ y ∈ C, there is a sequence x = x₀, …, x_n = y of elements of C such that, for each integer i where 0 ≤ i ≤ n − 1, x_ix_i+1 ∈ E. Clearly, an isolated vertex of G constitutes a connected component of G. The graph G is connected if it has exactly one connected component.

The Cartesian product G□H of graphs G = (V₁, E₁) and H = (V₂, E₂) is the graph such that the vertex-set is V(G) × V(H) and (a, x)(b, y) ∈ E(G□H) whenever ab ∈ E₁ and x = y or a = b and xy ∈ E₂. For any h ∈ V₂, the subgraph of G□H induced by V₁ ×{h} is called a G-fiber and is denoted by G^h. The H-fiber could be defined similarly. Figure 1 gives an example of the Cartesian product of two graphs.

Consider the following immediate observation.

1.1 Observation

1. A Cartesian product of two graphs is connected if and only if both factors are connected.

2. Every proper module of a Cartesian product of two connected graphs is included in a fiber.

The present work focuses on the primality and the Cartesian product of graphs. In the last few years, graph products have emerged again as a flourishing topic in graph theory. It has always been a good method to construct large graphs from small ones. Such products include: the Categorical product [8], the Kronecker product [9], the Cardinal product [10] and the Cartesian product [11–13]. The most widely used one that offers interesting problems may be the Cartesian product, which was first introduced by Sabidussi [14]. These types of graph products and other ones have been the subject of several papers [8,9,15–17]. On the other hand, the concept of primality has also been fundamental in the study of finite structures. Many questions on primality revolve around the study of its hereditary aspect in the graphs. Some papers have appeared along these lines [2,4,18–25]. In the case of graphs a first result dates back to D. P. Sumner [26]: Every prime graph G with at least 4 vertices has a subgraph which is a P₄. After that, A. Ehrenfeucht and G. Rozenberg [3] affirmed that the prime graphs have the following ascendant hereditary property: Let X be a subset of a prime graph G such that G[X] is prime. If |V(G) \ X|≥ 2, then there are x ≠ y ∈ V(G) \ X such that G[X ∪ {x, y}] is prime. Later, J. H. Schmerl and W. T. Trotter [5] established the following decending. For each prime graph G with at least 6 vertices, there are a ≠ b ∈ V(G) such that G − {a, b} is prime. To prove this result, the authors have introduced and described the critical graphs.

Motivated by works obtained on ”the Cartesian product of graphs” and ”the primality”, H. Kheddouci proposed to find a link between the two notions. Actually, he asked about the primality of Cartesian product and its subgraphs. This paper provides answers to questions asked by Kheddouci.

First, we establish that the primality of the Cartesian product of two graphs is essentially guaranteed by the connectedness of the two graphs. We obtain the following.

Theorem 1.2

Given two non-trivial connected graphs G₁ = (V₁, E₁) and G₂ = (V₂, E₂) such that |V₁|≥ 3 or |V₂|≥ 3, then the Cartesian product G₁□G₂ is prime.

Using Observation 1.1, we deduce the following corollary.

Corollary 1.3

Given two non-trivial graphs G₁ = (V₁, E₁) and G₂ = (V₂, E₂) such that |V₁|≥ 3 or |V₂|≥ 3, the Cartesian product G₁□G₂ is connected if and only if it is prime.

Second, we characterize all the vertex pairs of a Cartesian product of two connected graphs such that their suppression results in a prime graph. We obtain the following.

Theorem 1.4

Let G₁ = (V₁, E₁) and G₂ = (V₂, E₂) be two connected graphs such that |V₁|≥ 3 and |V₂|≥ 3. Consider distinct vertices a = (x_a, y_a) and b = (x_b, y_b) of G₁□G₂.

The pair {a, b} is not an edge of the graph I(G1□G2) if and only if one of the following conditions is satisfied.

• 1. There are distinct vertices x₀, x₁ and x₂ of G₁ and distinct vertices y₀, y₁ and y₂ of G₂ such that NG1(x0)={x1}, x2∈NG1(x1), NG2(y0)={y1}, y2∈NG2(y1) and

{a,b}={(x0,y1),(x1,y0)}if|NG1(x1)|≥3 or |NG2(y1)|≥3or{(xi,yj),(xj,yi)} where i≠j∈{0,1,2}otherwise.

• 2. Either x_a = x_b, x_a is the neighbor of a pendant vertex of G₁ and {y_a, y_b} is a duo of G₂, or y_a = y_b, y_a is the neighbor of a pendant vertex of G₂ and {x_a, x_b} is a duo of G₁.

For example, for G = P₃□P₃, E(I¯(P3□P3))={{(1,1),(3,3)},{(1,3),(3,1)},{(1,2),(3,2)},{(1,2),(2,1)},{(2,1),(3,2)},{(3,2),(2,3)},{(2,3),(1,2)},{(1,2),(3,2)},{(2,1),(2,3)}} (see Figure 2)

Note that Schmerl and Trotter [5] have confirmed that each prime graph with at least 6 vertices has a non-empty indecomposability graph. Theorem 1.4 describes the edges of the indecomposability graph of the Cartesian product of two connected graphs.

The following corollary is an immediate consequence of Theorem 1.4.

Corollary 1.5

Let G₁ = (V₁, E₁) and G₂ = (V₂, E₂) be two connected graphs such that |V₁|≥ 3 and |V₂|≥ 3. The graph I(G1□G2) is complete if and only if one of the following conditions is satisfied.

1. min (δ(G₁), δ(G₂)) ≥ 2.

2. There are i ≠ j ∈ {1, 2} such that δ(G_i) = 1, δ(G_j) ≥ 2 and G_j is duo-free.

Finally, we prove that all the vertices of the Cartesian product of two connected graphs with at least 3 vertices are not critical. We obtain the following.

Theorem 1.6

Given two connected graphs G₁ = (V₁, E₁) and G₂ = (V₂, E₂) such that |V₁|≥ 3 and |V₂|≥ 3, then G₁□G₂ has no critical vertex.

The text is organized as follows: Section 2 focuses on the proof of Theorem 1.2 while Section 3 is devoted to the proof of Theorem 1.4. However, Section 4 covers the third main result.

2. Proof of Theorem 1.2

Let two non-trivial connected graphs G₁ = (V₁, E₁) and G₂ = (V₂, E₂) such that |V₁|≥ 3 or |V₂|≥ 3. Denote G = G₁□G₂, V = V(G₁□G₂) and E = E(G₁□G₂). Let us prove that G₁□G₂ is prime. On the contrary, suppose that G₁□G₂ is decomposable and consider I a nontrivial module of it. Since by Observation 1.1 G₁□G₂ is connected, I cannot be a connected component of it. Thus, there is z ∈ V \ I such that z— I. It follows from Observation 1.1 that I⊆V(G2xz)∪V(G1yz). Accordingly the two following cases have to be distinguished.

• Case 1. Either I∩V(G2xz)=∅ or I∩V(G1yz)=∅.

     Assume that I∩V(G2xz)=∅ (resp. I∩V(G1yz)=∅). Then, I⊆G1yz (resp. I⊆G2xz). Based on Observation 1.1, since G₁ (resp. G₂) is connected, then there is h ∈ V₁ (resp. h ∈ V₂) such that hx_z ∈ E₁ (resp. hy_z ∈ E₂). Using the definition of G₁□G₂ again, there is α∈V(G2h) (resp. α∈V(G1h)) such that α ≁ I; impossible.

• Case 2. I∩V(G2xz)≠∅ and I∩V(G1yz)≠∅.

In this case, there are two distinct elements u = (x_u, y_u) and v = (x_v, y_v) of I such that x_u = x_z, y_v = y_z and x_u ≠ x_v. Using the definition of G₁□G₂, the vertex t = (x_v, y_u) verifies tu ∈ E and tv ∈ E because z— {u, v}. In addition, since I⊆V(G2xz)∪V(G1yz), necessarily t ∉ I. Hence, t— I. Moreover, for each h∈(V(G2xz)∪V(G1yz))\{u,v}, th ∉ E and thus h ∉ I. Therefore, I = {u, v}. Consequently, if |V₂|≥ 3 (resp. |V₁|≥ 3), there is α∈V(G2xz) (resp. α∈V(G1yz)) such that αu ∈ E and αv ∉ E (resp. αu ∉ E and αv ∈ E); which is impossible.

3. Proof of Theorem 1.4

We start by the following obvious observations.

3.1 Observation

1. Let G be a connected graph with at least 3 vertices. Then for any vertices x and y of G, there is a subgraph (not necessarily an induced one) in G containing x and y and isomorphic to P_n where n ≥ 3.

2. Let G₁ and G₂ be two connected graphs with at least 3 vertices. Then for any distinct vertices a and b of G₁□G₂, there is a subgraph (not necessary an induced one) of G₁□G₂ containing a and b and isomorphic to P_n□P_m where n ≥ 3, m ≥ 3.

3. Let m and n be two integers such that m, n ≥ 3, P_n□P_m be a Cartesian product and a and b be two distinct vertices of P_n□P_m. Then

   • (P_n□P_m) − {a} is connected.

   • (P_n□P_m) − {a, b} is connected if and only if {a,b}∉{(1,2),(2,1)},{(n−1,1),(n,2)},{(1,m−1),(2,m)},{(n,m−1),(n−1,m)}.

Notice that the second assertion of Observation 3.1 is an immediate consequence of the first one.

Lemma 3.2.

Let G₁ = (V₁, E₁) and G₂ = (V₂, E₂) be two connected graphs such that |V₁|≥ 3 and |V₂|≥ 3 and let a and b be two distinct vertices of G₁□G₂. Then (G₁□G₂) − {a, b} is not connected if and only if there are x, x′ ∈ V₁ and y, y′ ∈ V₂ such that NG1(x)={x′}, NG2(y)={y′} and {a, b} = {(x′, y), (x, y′)}.

Proof. Consider two connected graphs G₁ = (V₁, E₁) and G₂ = (V₂, E₂) such that |V₁|≥ 3 and |V₂|≥ 3 and two distinct vertices a and b of G₁□G₂. Let G = G₁□G₂. Assume that G − {a, b} is not connected. Then there are two distinct vertices c = (x_c, y_c) and d = (x_d, y_d) of G − {a, b} such that there is no (c, d)-path in G − {a, b}. Based on Observation 3.1, there is a subgraph of G₁ (resp. G₂) containing x_c and x_d (resp. y_c and y_d) which is isomorphic to P_k where k ≥ 3 (resp. P_l where l ≥ 3). Hence, consider Pn′ (resp Pm′) where n, m ≥ 3, a longest path of G₁ (resp. G₂) containing x_c and x_d (resp. y_c and y_d) and H′=Pn′□Pm′.

If a∉V(H′) or b ∉ V(H′), then Observation 3.1 confirms that there is (c, d)-path in G − {a, b}; impossible. Presently, assume that both a and b are elements of V(H′). Given Observation 3.1, we have to consider only the case where {a,b}∈{(1,2),(2,1)},{(n−1,1),(n,2)},{(1,m−1),(2,m)},{(n,m−1),(n−1,m)}. Without loss of generality, let {a, b} = {(1, 2), (2, 1)}. To end the proof, it is enough to prove that NG1(1)={2} and NG2(1)={2}. On the contrary suppose that, for example, there is a vertex h = (x_h, y_h) such that xh∈NG1(1)\{2}. In case h ∉ V(H′), we obtain the subgraph defined on {1, 2, …, n, x_h} which is a path containing (x_c and x_d) and longer than Pn′, which contradicts the choice of Pn′. In case h ∈ V(H′), H′ − {a, b} is connected. Thus, there is a (c, d)-path in G − {a, b}; impossible.

Conversely, assume that there are x, x′ ∈ V₁ and y, y′ ∈ V₂ such that NG1(x)={x′}, NG2(y)={y′} and {a, b} = {(x′, y), (x, y′)}. It is clear that.

V(G) \{(x′, y), (x, y′), (x, y)} is a connected component of G − {a, b}. Therefore, G − {a, b} is not connected. □

3.2 Proof of theorem. 1.4

Let a = (x_a, y_a) and b = (x_b, y_b) be distinct elements of V(G₁□G₂). Denote G = G₁□G₂, V(G₁□G₂) = V and E(G₁□G₂) = E. Assume that ab∉E(I(G1□G2)). Hence, G − {a, b} is not prime. If G − {a, b} is not connected, then using Lemma 3.2, there are x, x′ ∈ V₁ and y, y′ ∈ V₂ such that NG1(x)={x′}, NG2(y)={y′} and {a, b} = {(x′, y), (x, y′)}. So by considering x₀ = x; x₁ = x′, y₀ = y; y₁ = y′ we obtain {a, b} = {(x₁, y₀), (x₀, y₁)} and thus the first condition of Theorem 1.4 is verified. Assume that G − {a, b} is connected. Let I be a non-trivial module of G − {a, b}. Obviously, I is not a connected component of G − {a, b}. Then there are u = (x_u, y_u) ∈ I and z = (x_z, y_z) ∈ V \ (I ∪ {a, b}) such that uz ∈ E. Based on the definition of G, x_u = x_z or y_u = y_z. Without loss of generality, we may assume that x_u = x_z. Since I is a module of G − {a, b}, z — I. Then I⊆V(G2xu)∪V(G1yz). We distinguish the two following cases.

• Case 1. Either I∩V(G1yz)=∅ or I∩V(G2xu)=∅.

     Without loss of generality, we may assume that I∩V(G1yz)=∅. Hence, necessarily I⊆V(G2xu). Since G₁ is connected, there is h ∈ V₁ such that hx_u ∈ E₁. If |I|≥ 3, ∣G2h∣≥3. Thus, there is α∈V(G2h)\{a,b} such that α ≁ I; impossible. Consequently, |I| = 2. As I is a duo of G − {a, b}, NG1(xu)={h}. Let v = (x_u, y_v) ∈ I \{u}. It is clear that {y_u, y_v} is a duo of G₂ and {a, b} = {(h, y_u), (h, y_v)}, thus verifying the second condition of Theorem 1.4.

• Case 2. I∩V(G1yz)≠∅ and I∩V(G2xu)≠∅.

     In this case, there is v = (x_v, y_v) ∈ I such that y_v = y_z and x_v ≠ x_u. As G₁ and G₂ are connected, using the definition of G, there is t = (x_t, y_t) ∈ V such that x_t = x_v, y_t = y_u, tu ∈ E and tv ∈ E.

     First, prove that t∉{a, b}. On the contrary, suppose that t ∈ {a, b}. For instance, assume that t = a. Since G₁ is connected and |V₁|≥ 3, there is x_α ∈ V₁ \{x_u, x_v} such that x_αx_u ∈ E₁ or x_αx_v ∈ E₁. The two situations are studied as follows.

1. In case x_αx_u ∈ E₁. Since I⊆V(G2xu)∪V(G1yz), (x_α, y_u) ∉ I. Moreover, (x_α, y_u) ≁ I because (x_v, y_v)….(x_α, y_u) — (x_u, y_u). Thus, (x_α, y_u) = b. Since G₂ is connected and |V₂|≥ 3, there is y_β ∈ V₂ \{y_u, y_v} such that y_βy_u ∈ E₂ or y_βy_v ∈ E₂. First, assume that y_βy_v ∈ E₂, then (x_v, y_β) ∉ I because I⊆V(G2xu)∪V(G1yz). Moreover, based on the definition of G, (x_u, y_u)….(x_v, y_β) — (x_v, y_v); which contradicts the fact that I is a module of G − {a, b}. Second, assume that y_βy_u ∈ E₂ and yβ∉NG2(yv) because otherwise we return to the first step. Observe that (x_u, y_β) ∉ I, as z ∉ I, u ∈ I and (x_u, y_β)….(x_z, y_z) — (x_u, y_u). Furthermore, (x_u, y_β) ≁ I because (x_v, y_v)….(x_u, y_β) — (x_u, y_u); which contradicts the fact that I is a module of G − {a, b}.

2. In case x_αx_v ∈ E₁, we may also assume that x_αx_u ∉ E₁ because otherwise we return to the first situation. Obviously, (x_α, y_z)….(x_z, y_z) as x_αx_u ∉ E₁. Hence, (x_α, y_z) ∉ I. Moreover, (x_α, y_z) ≁ I because (x_u, y_u)….(x_α, y_z) — (x_v, y_v). Thus b = (x_α, y_z). Since G₂ is a connected graph with at least 3 vertices, there is y_β ∈ V₂ \{y_u, y_v} such that y_βy_u ∈ E₂ or y_βy_v ∈ E₂. First, assume that y_βy_v ∈ E₂. Then (x_v, y_β) ∉ I. Besides, using the definition of G, (x_u, y_u)….(x_v, y_β) — (x_v, y_v); which contradicts the fact that I is a module of G − {a, b}. Second assume that y_βy_u ∈ E₂ and y_βy_v ∉ E₂ because otherwise we return to the first step. Evidently, (x_u, y_β) ∉ I, since z ∉ I, v ∈ I and (x_v, y_β)….(x_z, y_z) — (x_u, y_u). Furthermore, (x_u, y_β) ≁ I, because (x_v, y_v)….(x_u, y_β) — (x_u, y_u); which contradicts the fact that I is a module of G − {a, b}.

In what remains, assume that t∉{a, b}. Since I⊆V(G2xu)∪V(G1yz), we have t ∉ I. Moreover, since u ∈ I and tu ∈ E, t — I. Using the definition of G, for each h∈(V(G2xu)∪V(G1yz))\{u,v}, th ∉ E and then h ∉ I. Therefore, I = {u, v}.

First, assume that dG1(xu)=1 and dG2(yv)=1. Then necessarily NG1(xu)={xv} and NG2(yv)={yu}. Since |V₁|≥ 3, |V₂|≥ 3 and {u, v} is a module of G − {a, b}, we obtain NG1yv(v)\{z}={a} or {b} and NG2xu(u)\{z}={a} or {b}. Thus, by considering, for example, x₀ = x_u, x₁ = x_v, x₂ = x_a, y₀ = y_v, y₁ = y_u and y₂ = y_b, we have {a, b} = {(x₂, y₀), (x₀, y₂)}, thus verifying the first condition of Theorem 1.4.

Second, assume that dG1(xu)≥2 or dG2(yv)≥2. Without loss of generality, assume that dG1(xu)≥2. Then there is h∈V(G1yu) such that h ∈ N_G(u) \{t} and h ≁ {u, v}. Therefore, h ∈ {a, b}. For instance, assume that h = a. Since |V₂|≥ 3 and G₂ is connected, there is w ∈ V₂ such that w∈NG2(yu) or w∈NG2(yv). To begin with, assume that w∈NG2(yu). Since (x_u, w) ≁ {u, v}, (x_u, w) = b. Necessarily, dG1(xv)=1 and dG1(xu)=2 because otherwise there is k ∈ V \{a, b} such that k ≁ {u, v}. Similarly, dG2(yv)=1 and dG2(yt)=2. Hence, by considering x₀ = x_v, x₁ = x_u, x₂ = x_a, y₀ = y_v, y₁ = y_u and y₂ = y_b, we obtain {a, b} = {(x₂, y₁), (x₁, y₂)}, thus verifying the first condition of Theorem 1.4. Now, we may assume that w∈NG2(yv) and w∉NG2(yu) because otherwise we return to the first situation. Since (x_v, w) ≁ {u, v}, (x_v, w) = b. Necessarily, dG1(xv)=1 and dG1(xu)=2 because otherwise there is k ∈ V \{a, b} such that k ≁ {u, v}. Similarly, dG2(yu)=1 and dG2(yv)=2. It results, by considering x₀ = x_v, x₁ = x_u, x₂ = x_a, y₀ = y_u, y₁ = y_v and y₂ = y_b that {a, b} = {(x₂, y₀), (x₀, y₂)}, thus verifying the first condition of Theorem 1.4.

Conversely, assume that one of the conditions of Theorem 1.4 is satisfied and let us prove that ab∉E(I(G)).

First, assume that the first condition is satisfied. Then there are distinct vertices x₀, x₁ and x₂ of G₁ and distinct vertices y₀, y₁ and y₂ of G₂ such that NG1(x0)={x1}, x2∈NG1(x1), NG2(y0)={y1}, y2∈NG2(y1) and

{a,b}={(x0,y1),(x1,y0)}if|NG1(x1)|≥3 or |NG2(y1)|≥3or{(xi,yj),(xj,yi)} where i≠j∈{0,1,2}otherwise.

Therefore, V \{(x₀, y₁), (x₁, y₀), (x₀, y₀)} or {(x₀, y₁), (x₁, y₀)} or {(x₁, y₁), (x₀, y₀)} is a non-trivial module of G − {a, b}. Thus, ab∉E(I(G)).

Second, assume that the second condition is satisfied. If x_a = x_b, x_a is the neighbor of a pendant vertex of G₁ and {y_a, y_b} is a duo of G₂ (resp. If y_a = y_b, y_a is the neighbor of a pendant vertex of G₂ and {x_a, x_b} is a duo of G₁), in this case, consider x₁ (resp. y₁) to be a pendant vertex of G₁ (resp. G₂) such that NG1(x1)={xa} (resp. NG2(y1)={ya}). Clearly, {(x₁, y_a), (x₁, y_b)} (resp. {(x_a, y₁), (x_b, y₁)}) is a non-trivial module of G − {a, b}. Thus, ab∉E(I(G)).□

4. Proof of Theorem 1.6

The proof of Theorem 1.6 is an immediate consequence of Theorem 1.2, the following result due to Y. Boudabbous and P. Ille and also the lemma below.

Lemma 4.1.

[21] Let G be a prime graph with at least 5 vertices. For each critical vertex x of G, |NI(G)(x)|≤2.

Lemma 4.2.

Let G₁ = (V₁, E₁) and G₂ = (V₂, E₂) be two connected graphs such that |V₁|≥ 3 and |V₂|≥ 3. Then for each vertex a ∈ V(G₁□G₂), |NI(G1□G2)(a)|≥3.

Proof. Let a = (x_a, y_a) ∈ V(G₁□G₂) and note that G = G₁□G₂, V(G₁□G₂) = V and E(G₁□G₂) = E. The result is obvious when |NI(G)(a)|=|V|−1. Then assume that |NI(G)(a)|<|V|−1. Thus, there is b = (x_b, y_b) ∈ V \{a} such that ab∉E(I(G)). Then one of the conditions of Theorem 1.4 is satisfied.

First, assume that there are distinct vertices x₀, x₁ and x₂ of G₁ and distinct vertices y₀, y₁ and y₂ of G₂ such that NG1(x0)={x1}, x2∈NG1(x1), NG2(y0)={y1}, y2∈NG2(y1) and

{a,b}={(x0,y1),(x1,y0)}if|NG1(x1)|≥3 or |NG2(y1)|≥3or{(xi,yj),(xj,yi)} where i≠j∈{0,1,2}otherwise.

To begin with, assume that {a, b} = {(x₀, y₁), (x₁, y₀)}. For instance, we may assume that a = (x₀, y₁) and b = (x₁, y₀). Consider the three vertices c = (x₀, y₀), d = (x₀, y₂) and e = (x₁, y₁) of G. Since {y_a, y₀}, {y_a, y₂} are not duos of G₂ and {x_a, x₁} is not a duo of G₁, then using Theorem 1.4, the vertices c, d and e are neighbors of a in I(G) and thus |NI(G)(a)|≥3.

Now, assume that {a, b} ∈ {{(x₀, y₂), (x₂, y₀)}, {(x₁, y₂), (x₂, y₁)}}. If {a, b} = {(x₀, y₂), (x₂, y₀)}, for example, we may assume that a = (x₀, y₂) and b = (x₂, y₀). Consider the two distinct vertices c = (x₁, y₂) and d = (x₀, y₁) of G. Since {y_a, y₁} is not a duo of G₂ and {x_a, x₁} is not a duo of G₁, then based on Theorem 1.4 the vertices c and d are neighbors of a in I(G). Presently, consider the vertex e = (x₀, y₀) of G. Since NG1(x0)={x1}, x₀ is not a neighbor of a pendant vertex of G₁. So using Theorem 1.4, e is neighbor of a in I(G) and thus |NI(G)(a)|≥3.

At present, assume that {a, b} = {(x₁, y₂), (x₂, y₁)}. For instance, consider a = (x₁, y₂) and b = (x₂, y₁). Let c = (x₀, y₂), d = (x₂, y₂) and e = (x₁, y₁). Since {y_a, y₁} is not a duo of G₂ and {x_a, x₀} and {x_a, x₂} are not duos of G₁, then given Theorem 1.4, the vertices c, d and e are neighbors of a in I(G) and thus |NI(G)(a)|≥3.

Second, either x_a = x_b, x_a is the neighbor of a pendant vertex of G₁ and {y_a, y_b} is a duo of G₂, or y_a = y_b, y_a is the neighbor of a pendant vertex of G₂ and {x_a, x_b} is a duo of G₁. Without loss of generality, we may assume that x_a = x_b, x_a is the neighbor of a pendant vertex of G₁ and {y_a, y_b} is a duo of G₂. Let x₀ ∈ V₁ such that NG1(x0)={xa}. As G₁ is a connected graph and |V₁|≥ 3, there is x1∈NG1(xa)\{x0}. Let c = (x₀, y_a) and d = (x₁, y_a). Observe that {x₀, x_a} and {x_a, x₁} are not duos of G₁, then c,d∈NI(G)(a) follows from Theorem 1.4. Since G₂ is connected, |V₂|≥ 3 and {y_a, y_b} is a duo of G₂, there is y₀ ∈ V₂ such that y₀— {y_a, y_b}.

If y_ay_b ∈ E₂, consider e = (x₀, y₀). If y₀ is not a neighbor of a pendant vertex of G₂, then based on Theorem 1.4, e∈NI(G)(a) and thus |NI(G)(a)|≥3. In case y₀ is a neighbor of a pendant vertex y_α of G₂, {y_a, y_α} is not a duo of G₂ because y_ay_b ∈ E₂ and y_α is a pendant vertex. Thus, Theorem 1.4 implies that (xa,yα)∈NI(G)(a) and then |NI(G)(a)|≥3. If y_ay_b ∉ E₂, consider e = (x_a, y₀). It is clear that {y_a, y₀} is not a duo of G₂, therefore, based on Theorem 1.4, e∈NI(G)(a) and thus |NI(G)(a)|≥3. □

Figures

Figure 1

G1□G2

Figure 2

P₃□P₃ and I¯(P3□P3)