Simple-intersection graphs of rings

1.   Introduction

One of the active research fields of algebraic graph theory is the association of a graph to an algebraic structure. The significance of this topic has led many authors to study the interplay between the graph theoretic properties, such as diameter, girth, cliques, connectedness, dominating sets, etc, and the algebraic properties of the underlined algebraic structure. A significant amount of research has been devoted to the study of algebraic structures and their associated graphs. We mention here, Cayley graph of a commutative ring ^[11], a zero-divisor graph for a commutative ring ^[4], unit graphs associated with rings ^[5], and comaximal graphs associated with rings ^[13].

The intersection graph of ideals of a ring ^[7] is another important graph associated to a ring. The intersection graph of ideals of a ring $R$ is a graph having the set of all nonzero ideals of $R$ as its vertex set and two distinct vertices $I$ and $J$ are adjacent if and only if $I \cap J$ is non-trivial (non-zero). The intersection-graph of ideals was studied by a large number of mathematicians, in which they obtained many of its properties and linked them to the properties of rings as demonstrated in ^{[1,2,3,10,16,17,18]}. The intersection-graph of ideals of rings gave birth to many graphs associated to rings and other algebraic structures as one can see in ^{[12,13,14,15]}. For more information about this topic, we recommend the survey on the intersection-graph of ideals of rings ^[8]. In this paper, we define the following graph.

Definition 1. Let $R$ be a ring with unity $1 \neq 0$. The simple-intersection graph of $R$, denoted by $GS(R)$, is defined to be a simple graph whose vertices are the nonzero ideals of $R$, and two vertices $I$ and $J$ are adjacent, and we write $I \leftrightarrow J$, if and only if $I \cap J$ is a nonzero simple ideal.

For example, consider the ring $\mathbb{Z}_4$. The nonzero ideals of $\mathbb{Z}_4$ are $\mathbb{Z}_4$ and $2\mathbb{Z}_4 \cong \mathbb{Z}_2$. Obviously, $GS(\mathbb{Z}_4)$ is $\mathbb{Z}_4 \leftrightarrow 2\mathbb{Z}_4$. Clearly, the simple-intersection graph is a subgraph of the intersection graph of ideals of $R$. We study several properties of this graph such as connectedness, Euler circuits, regularity, girth, cliques, the "bipartite" property, dominating sets. Moreover, we relate these concepts with various algebraic properties of the ring $R$. For instance, we show that the girth of $GS(R)$ equals one of the three values $3$, $4$, or $\infty$. We also show that the diameter of $GS(R)$ does not exceed $4$ and never equals $3$. Furthermore, we give explicit formulas to compute the clique and domination numbers of $GS(R)$. Besides, a necessary and sufficient conditions for $GS(R)$ to be bipartite are provided. We give many examples to illustrate the concepts discussed here, and provide counterexamples for expected results. This work is exhibited in Sections 3 through 7. Some preliminaries from ring theory and graph theory are listed in Section 2.

We shall apply our results in algebra to develop new theories in graph theory and vise versa. Also, we will utilize our results to solve some coloring and optimization problems, which will be our next project.

2.   Preliminaries

This section presents a quick review of rings and graphs that are important in this paper. All notions presented here could be found in ^[6,9]. In this paper, all rings are assumed to be nonzero rings with unity $1 \neq 0$ and are not necessarily commutative. Also, the ideals are considered to be left ideals. We first start with some preliminaries from Ring Theory.

Definition 2. An ideal $I$ of a ring $R$ is said to be simple (or minimal) if $I$ and $\{0\}$ are the only ideals included in $I$.

Definition 3. The direct sum of simple ideals of a ring $R$ is called a semisimple ideal. We call each simple ideal in the decomposition of a semisimple ideal, a component.

Obviously, a simple ideal is semisimple with one component. On the other hand, every ideal of a semisimple ideal is semisimple.

Definition 4. The socle of $R$, denoted by $Soc(R)$, is defined to be the sum (precisely, the direct sum) of all nonzero simple ideals of $R$. If $R = Soc(R)$, we call $R$ a semisimple ring.

Definition 5. A proper ideal $I$ of a ring $R$ is said to be maximal if $I$ is not contained in another proper ideal of $R$.

Definition 6. A ring $R$ is said to be Artinian if it satisfies the descending chain condition on ideals.

Theorem 7. A ring $R$ is Artinian if and only if Every nonzero ideal contains a nonzero simple ideal.

As a direct corollary from Theorem 7, semisimple rings are Artinian.

Next, we turn to preliminaries from Graph Theory concerning undirected graphs. In what follows, $G$ denotes an undirected graph. The number of vertices of $G$ is called the order the graph $G$. The set of vertices of $G$ is denoted by $Ver[G]$. If two vertices $u$ and $v$ are adjacent, we express that symbolically by $u \leftrightarrow v$.

Definition 8. Let $v$ be a vertex in $G$. The neighborhood $N(v)$ of $v$ is the set of all vertices adjacent to $v$, i.e., the set of all vertices each of which is linked to $v$ by an edge.

If $G$ is a simple undirected graph, then $v \notin N(v)$. If $N(v) = \emptyset$, then $v$ is an isolated vertex.

Definition 9. The degree of a vertex $v$ of $G$ is the number of edges incident to $v$, i.e., going out of $v$. The degree of $v$ is denoted by $deg_G(v)$ (or $deg(v)$ if there is no confusion with the underlined graph). The minimum of the degrees of the vertices is denoted by $\delta(G)$, while the maximum of the degrees of the vertices is called the degree of the graph and is denoted by $\Delta(G)$.

When $G$ is a simple graph, then $deg(v) = |N(v)|$, where $|N(v)|$ means the cardinality of $N(v)$. Hence, $v$ is isolated if and only if $deg(v) = 0$.

Definition 10. A graph whose vertices have equal degrees is called a regular graph.

It is obvious to see that a graph $G$ is regular if and only if $\Delta(G) = \delta(G)$.

Definition 11. Let $v$ and $u$ be two vertices of $G$. The length of a path between $v$ and $u$ is the number of edges forming the path. The distance $d(u, v)$ between $v$ and $u$ is the length of a shortest path between them. The diameter of $G$, denoted by $diam(G)$, is defined to be the supremum of the set $\{d(u, v): u, v \in Ver[G]\}$.

Definition 12. A graph $G$ is path connected if there is a path between any two vertices of $G$.

Definition 13. A graph is said to be complete if it is a simple graph and every pair of vertices are adjacent. The complete graph on $n$ vertices is denoted by $K_n$.

Definition 14. A subgraph of $G$ which is a complete graph is called a clique of $G$. The order of a largest clique (i.e., a clique with the largest number of vertices) is called the clique number of $G$ and it is denoted by $\omega(G)$.

Definition 15. By the girth of $G$, we mean the length of a shortest cycle in $G$. The girth of $G$ is denoted by $g(G)$. If $G$ has no cycles, then we write $g(G) = \infty$.

Definition 16. An Euler path of $G$ is a path consisting of all edges of $G$ without repetition. If an Euler path is closed, then it is called an Euler circuit.

Theorem 17. A graph has an Euler path if and only if every vertex has an even degree. However, a graph has an Euler circuit if and only if exactly two vertices has an odd degree.

Definition 18. A dominating set $D$ of $G$ is a nonempty subset of $Ver[G]$ such that each vertex of $G$ is either in $D$ or adjacent to a vertex in $D$. The infimum of the set $\{|D|: D \; { is\; a\; dominating \; set\; of\; }G\}$ is called the domination number of $G$ and is denoted by $\gamma(G)$.

Definition 19. A simple graph $G$ is called bipartite if we can partition $Ver[G]$ into two disjoint nonempty subsets (each subset is called a part) such that the vertices belonging to the same subset are not adjacent to each other. A complete bipartite graph is a bipartite graph where each vertex in one part is adjacent to each vertex in the other part. A complete bipartite graph is denoted by $K_{m, n}$ or $K_{n, m}$, where $m$ is the cardinality of one part and $n$ is the cardinality of the other part.

The "bipartite" problem is one of the coloring problems, which investigates the possibility to color the vertices of a simple undirected graph using two colors such that no adjacent vertices have the same color. This is possible for a simple undirected graph if and only if it is bipartite.

More preliminaries will be added in the next sections as needed.

3.   Cycles and girth of $GS(R)$

In this section, we study the cycles and girth of $GS(R)$. Some parts of this section have the same flow of similar results of other associated graphs found earlier in the literature, while other parts have new approaches.

Recall that a null graph is a graph whose vertices are not adjacent to each other (i.e., edgeless graph).

Theorem 20. The graph $GS(R)$ is a null graph if and only if $R$ is a simple ring or $R$ has no nonzero simple ideals.

Proof. Assume $GS(R)$ is a null graph. Suppose for contrary that $R$ is not simple and it contains a nonzero simple ideal $I$. Then $R \leftrightarrow I$ and hence $GS(R)$ is not null, which is a contradiction to the hypothesis "$GS(R)$ is a null graph". The converse is easy.

Example 21. $GS(\mathbb{Z})$ and $GS(\mathbb{Z}_2)$ are null.

Remark 22. In $GS(R)$, $I \leftrightarrow R$ if and only if $I$ is a nonzero simple ideal of $R$. So the subgraph consisting of $R$ with all nonzero simple ideals of $R$ is a star graph with center $R$, and hence $deg(R)$ equals the number of nonzero simple ideals of $R$. Thus, if $R$ is semisimple with $n$ components, then $deg(R) = n$. On the other hand, if $I$ is a nonzero simple ideal of $R$ and $J$ is an ideal of $R$, then $I \leftrightarrow J$ if and only if $I \subsetneq J$. Moreover, every pair of different nonzero simple ideals is not adjacent, or equivalently, the subgraph of $GS(R)$ consisting of nonzero simple ideals is a null graph.

Next, we study the cycles of $GS(R)$. We show that the cycles with length at least $4$ has only two special patterns. Afterward, we demonstrate that the girth of $GS(R)$ is either $\infty$, $3$, or $4$.

Theorem 23. The graph $GS(R)$ has a cycle of length $3$ if and only if $GS(R)$ contains at least two adjacent non-simple ideals.

Proof. Assume that the graph $GS(R)$ has a cycle of length $3$, say $I \leftrightarrow J \leftrightarrow K \leftrightarrow I$. By Remark 22, at most one of the vertices is simple. So, at least two of the vertices in this cycle are adjacent non-simple ideals of $R$. For the converse, let $I$ and $J$ be two different nonzero non-simple ideals such that $I \cap J$ is nonzero simple. Then we have the cycle $I \leftrightarrow J \leftrightarrow I \cap J \leftrightarrow I$.

Theorem 24. If the graph $GS(R)$ has a cycle, then either $g(GS(R)) = 3$ or $g(GS(R))$ is even.

Proof. Assume that $GS(R)$ has the cycle $I_1 \leftrightarrow I_2 \leftrightarrow \ldots \leftrightarrow I_n \leftrightarrow I_1$, and $n > 3$, with the least length. By Remark 22 and Theorem 23, if two vertices in the cycle are adjacent, then one of them is nonzero simple and the other is non-simple. In other words, the vertices of the cycle alternate between simple and non-simple ideals. Without loss of generality, assume $I_1$ is simple. Then $I_2$ is not simple, $I_3$ is simple, $I_4$ is not simple, and so on. Thus, for each $1 \leq k \leq n$, $I_k$ is simple if $k$ is odd, and $I_k$ is not simple if $k$ is even. If n is odd, then $I_n$ is simple and this implies $I_{n+1} = I_1$ is not simple which contradicts the assumption that $I_1$ is simple. We conclude that $n$ is even. Since the length of a cycle equals $n$, the number of its vertices, we get that the length of the cycle is even. As a result, any cycle in $GS(R)$ has either a length of $3$ or has an even length. Consequently, $g(GS(R)) = 3$ or $g(GS(R))$ is even.

Corollary 25. Let $R$ be a semisimple ring. If $R$ has more than two components, then $g(GS(R)) = 3$. Otherwise, $g(GS(R)) = \infty$.

Proof. Assume $R$ has at least three components. Let $I \oplus J \oplus K$ be a semisimple ideal of $R$. Then $I \oplus J$ and $J \oplus K$ are nonzero different non-simple ideals whose intersection is the simple ideal $J$. By Theorem 23, $GS(R)$ has a cycle of length $3$, and hence $g(GS(R)) = 3$. The rest of the proof is easy.

Remark 26. The proof of Theorem 24 displays a technique to build a cycle of a shortest length more than $3$ as illustrated in the next example.

Example 27. Let $R = I \oplus J \oplus K \oplus T$ be a semisimple ring with 4 components. Then $P_1: I \leftrightarrow I \oplus J \oplus K \leftrightarrow J \leftrightarrow I \oplus J \leftrightarrow I$ and $P_2: I \oplus T \leftrightarrow J \oplus T \leftrightarrow I \oplus J \leftrightarrow I \oplus T$ are two different cycles of length $4$. Notice that $P_1$ was constructed using the technique applied in the proof of Theorem 24; that is the vertices of $P_1$ alternate between simple and non-simple ideals. However, $P_2$ was built in different way where all its vertices are not simple ideals.

Example 28. Given the ring $\mathbb{Z}_4 \oplus \mathbb{Z}_2$, the cycle $\mathbb{Z}_4 \oplus \mathbb{Z}_2 \leftrightarrow 0 \oplus \mathbb{Z}_2 \leftrightarrow \mathbb{Z}_2 \oplus \mathbb{Z}_2 \leftrightarrow \mathbb{Z}_2 \oplus 0 \leftrightarrow \mathbb{Z}_4 \oplus \mathbb{Z}_2$ is a shortest cycle in $GS(\mathbb{Z}_4 \oplus \mathbb{Z}_2)$. Therefore, $g(GS(\mathbb{Z}_4 \oplus \mathbb{Z}_2)) = 4$.

The following theorem is a natural extension of the previous work.

Theorem 29. The girth of $GS(R)$ equals $\infty$, $3$, or $4$.

Proof. According to Theorem 23, if $R$ has no nonzero simple ideals, or $R$ is simple, then $g(GS(R)) = \infty$. Assume now that $R$ includes exactly one nonzero simple ideal $I$. If $I$ is a maximal ideal (which is possible if all elements of $R$ outside $I$ are units), then $GS(R)$ is just $R \leftrightarrow I$ and hence $g(GS(R)) = \infty$. If $I$ is not a maximal ideal, then $I$ is included in proper non-simple ideals. At this point, if $I$ is included in a unique proper non-simple ideal $J$, then $R \leftrightarrow I$ and $J \leftrightarrow I$ are the only paths in $GS(R)$ and hence $g(GS(R)) = \infty$. However, if $I$ is included in more than one proper non-simple ideal, then either there are two proper non-simple ideals intersect at $I$, which implies by Theorem 23 that $g(GS(R)) = 3$, or no two proper non-simple ideals intersect at $I$, which implies $GS(R)$ is a star graph with center $I$ and hence $g(GS(R)) = \infty$. Next, assume that $R$ has at least two different nonzero simple ideals. Let $I$ and $J$ be two different nonzero simple ideals. We distinguish between two cases. In the first case, assume $R = I \oplus J$. By Corollary 25, $g(GS(R)) = \infty$. In the second case, assume that $R \neq I \oplus J$. Then, the cycle $R \leftrightarrow I \leftrightarrow I \oplus J \leftrightarrow J \leftrightarrow R$ is a cycle of length $4$. The latter cycle has the least length unless $R$ possesses two different non-simple ideals whose intersection is a nonzero simple ideal, which yields by Theorem 23 the existence of a cycle of length $3$.

4.   Paths, connectedness, and completeness

The work in this part of the paper describes the paths of $GS(R)$ and gives the necessary and sufficient conditions for a ring to have a path connected simple-intersection graph. In addition, we give the necessary and sufficient conditions for $GS(R)$ to be a complete graph.

Lemma 30. The distance between two nonzero simple ideals in $GS(R)$ is $2$.

Proof. Let $I$ and $J$ be two nonzero simple ideals of $R$. Then $I$ and $J$ are not adjacent, however, they are connected by the path $I \leftrightarrow R \leftrightarrow J$ which is a shortest path between $I$ and $J$. Therefore, $d(I, J) = 2$.

Theorem 31. The graph $GS(R)$ is path connected if and only if R is an Artinian ring.

Proof. Suppose $GS(R)$ is path connected and $R$ is not simple. Let $I$ be a nonzero ideal of $R$. Then, there is a path from $I$ to $R$. If the path has a length equal to $1$, then $I \leftrightarrow R$ and hence $I$ is a simple ideal. If the path has a length of at least $2$, then there exists an ideal $J \neq R$ such that $J \leftrightarrow I$. Thus, $I \cap J$ is a nonzero simple ideal contained in $I$. Since every nonzero ideal contains a nonzero simple ideal, we conclude that $R$ is Artinian.

For the converse, assume $R$ is an Artinian ring. Let $I$ and $J$ be two nonzero ideals. Then, there exist nonzero simple ideals $K$ and $L$ such that $K \subseteq I$ and $L \subseteq J$. The path $I \leftrightarrow K \leftrightarrow K \oplus L \leftrightarrow L \leftrightarrow J$ connects $I$ and $J$. Consequently, $GS(R)$ is path connected.

Corollary 32. If $R$ is Artinian, and $I$ and $J$ are nonzero ideals, then $1 \leq d(I, J) \leq 4$.

Proof. Suppose $R$ is Artinian, and $I$ and $J$ are nonzero ideals. By Theorem 31, $d(I, J)\geq 1$. We consider different cases. In the first case, assume that both ideals are simple, by Lemma 30, we have $d(I, J) = 2$. In the second case, assume exactly one of them, say $I$, is simple. If $I \subset J$, then $I \leftrightarrow J$ and hence $d(I, J) = 1$. However, if $I \nsubseteq J$, then $I \cap J = 0$. Let $0 \neq K \subsetneq J$ be a simple ideal. Then, $I \leftrightarrow I \oplus K \leftrightarrow J$ is the shortest path between $I$ and $J$. So, $d(I, J) = 2$. In the third case, assume neither of $I$ and $J$ is simple. If $I \cap J$ is nonzero simple, then $I \leftrightarrow J$ and hence $d(I, J) = 1$. If $I \cap J$ is not simple, then it contains a nonzero simple ideal K. The path $I \leftrightarrow K \leftrightarrow J$ is the shortest path between $I$ and $J$ and hence $d(I, J) = 2$. If $I \cap J = 0$, then the path $I \leftrightarrow K \leftrightarrow K \oplus L \leftrightarrow L \leftrightarrow J$ is the shortest path between $I$ and $J$, where $K$ and $L$ are nonzero simple ideals of $R$ contained in $I$ and $J$, respectively. Hence $d(I, J) = 4$.

Recall that a path component of a graph is the largest path connected subgraph (i.e., a connected subgraph that is not a subgraph of another connected subgraph). A graph may have more than one path component. A graph is connected if and only if the path component is unique. Furthermore, the diameter of a graph equals the supremum of the diameter of its path components.

Theorem 33. In $GS(R)$, all the vertices with positive degree lie in one path component which is the path component containing $R$. The rest of components are isolated vertices.

Proof. A discussion resembling that in the proof of Corollary 32 leads us to the fact that any vertex of positive degree is connected to $R$ by a path of length less than $3$.

Definition 34. The component of $R$ mentioned in Theorem 33 is called the $R$-component of $GS(R)$.

According to Theorem 33, we can, in many situations, identify $GS(R)$ with its $R$-component, since we can carry the discussion of a disconnected $GS(R)$ to its $R$-component.

The proof of the next corollary follows easily from Corollary 32 and Theorem 33.

Corollary 35. $1 \leq diam(GS(R)) \leq 4$. Moreover, $diam(GS(R)) = 1$ if and only if the $R$-component of $GS(R)$ is a complete graph consisting of at least two vertices.

Theorem 36. The graph $GS(R)$ is complete if and only if $R$ has a unique proper nonzero ideal. Actually, $GS(R)$ is $K_2$.

Proof. Suppose for contrary that $R$ has at least two nonzero proper ideals. Let $I$ and $J$ be such ideals. If both of them are simple, then $I$ is not adjacent to $J$, and this contradicts that $GS(R)$ is complete. If either $I$ or $J$ is not simple, say $I$, then $R$ is not adjacent to $I$, and again this contradicts that $GS(R)$ is complete. For the converse, suppose $R$ has a unique nonzero proper ideal $I$. Then $Ver[GS(R)] = \{R, I\}$. Since $I$ is simple, we have $I \leftrightarrow R$ and hence $GS(R)$ is complete and $GS(R)$ is $K_2$.

The following corollary is a straight forward result from Theorem 36.

Corollary 37. If $R$ is a semisimple ring, then $GS(R)$ is not complete.

Example 38. $GS(\mathbb{Z}_4)$ is $K_2$, while $GS(\mathbb{Z}_2 \oplus \mathbb{Z}_2)$ is not complete.

We have seen so far that if $GS(R)$ is not a null graph, then $1 \leq diam(GS(R)) \leq 4$. Surprisingly, $diam(GS(R))$ never reaches $3$ as demonstrated in the next theorem.

Theorem 39. We have $diam(GS(R)) \neq 3$.

Proof. Without loss of generality, suppose $GS(R)$ is not a null graph. The proof is carried out by contradiction. Assume there exist two nonzero ideals of $R$ such that $d(I, J) = 3$. This is interpreted by saying that the shortest path connecting $I$ and $J$ has a length equal to 3. Let $I \leftrightarrow K \leftrightarrow L \leftrightarrow J$ be such a shortest path. Thus we have $I$ is not adjacent to $J$, $J$ is not adjacent to $K$, $I$ is not adjacent to $L$, and at least one of $K$ and $L$ is not simple. We have $I \cap K$ and $J \cap L$ are nonzero simple ideals. Also, $I \cap J \cap L = 0$ (because if not, then the simplicity of $J \cap L$ implies $I \cap J \cap L = J \cap L$, which in turn implies $J \cap L\subseteq I$, which yields that $I$ and $J$ are connected by the path $I \leftrightarrow (J \cap L) \leftrightarrow J$ of length 2. This contradicts that $d(I, J) = 3$). Similarly, we obtain that $J \cap I \cap K = 0$. Now, let $T = (I \cap K) \oplus (J \cap L)$. Then $I \cap T = I \cap K$ and $J \cap T = J \cap L$ which are nonzero simple ideals. So, we have the path $I \leftrightarrow T \leftrightarrow J$ is a path connecting $I$ and $J$ of length equal to 2, which is a contradiction to the assumption $d(I, J) = 3$. In conclusion, we obtain that $d(I, J) \neq 3$.

5.   The "bipartite" property

This section studies the conditions which make $GS(R)$ bipartite. Since the null graph is obviously bipartite, the importance here in our consideration is the non-null $GS(R)$. Recall that $GS(R)$ is not null if and only if $R$ possesses a proper nonzero simple ideal. We start with the following corollary which is an outcome of Section 3.

Corollary 40. If $3 < g(GS(R)) < \infty$, then $GS(R)$ is bipartite.

Proof. Suppose $3 < g(GS(R)) < \infty$. Following the same argument of the proof of Theorem 24, we obtain that no nonzero simple ideals are adjacent to each other and no non-simple ideals are adjacent to each other. Thus, the graph $GS(R)$ is bipartite with parts $W_1$ consisting of all nonzero simple ideals of $R$, and $W_2$ consisting of all non-simple ideals of $R$.

Example 41. In Example 28, $GS(\mathbb{Z}_4 \oplus \mathbb{Z}_2)$ is bipartite by Corollary 40.

Definition 42. Let $I\neq 0$ be an ideal of $R$. By $GS(R, I)$, we mean the subgraph of $GS(R)$ whose vertices are $I$ and all vertices adjacent to $I$ along with the edges incident to these vertices. We call $GS(R, I)$ the local simple-intersection graph of $I$.

Theorem 43. The graph $GS(R)$ is bipartite if and only if $GS(R, I)$ is a star graph with center $I$, for every nonzero simple ideal $I$ of $R$.

Proof. Assume $GS(R)$ is a bipartite graph. Without lose of generality, assume $GS(R)$ is not a null graph. Let $V$ and $W$ be a bipartition. Let $I$ be a nonzero simple ideal of $R$. Suppose that $I \in V$. Then none the vertices of $N(I)$ belongs to $V$ and therefore they belong to $W$. Thus, all vertices of $N(I)$ are pairwise nonadjacent. This means, that $GS(R, I)$ is a star graph with center $I$.

For the converse, assume that $GS(R, I)$ is a star graph with center $I$, for every nonzero simple ideal $I \subseteq R$. Let $V$ be the set of all nonzero simple ideals of $R$, and $W$ be the set of the remaining (non-simple) ideals of $R$. By Remark 22, we have the vertices of $V$ are not adjacent to each other. On the other hand, let $J, K \in W$. Assume, for contrary, that $J \leftrightarrow K$. Then, $J\cap K$ is a nonzero simple ideal. Hence, $J, K \in Ver[GS(R, J \cap K)] = N(J \cap K)$, which contradicts that $GS(R, J \cap K)$ is a star graph with center $J \cap K$. Thus, we obtain that any two vertices of $W$ are not adjacent. Consequently, $GS(R)$ is bipartite with bipartition $V$ and $W$.

In General, a bipartite graph may have more than one bipartition. However, the existence of the $(V, W)$-bipartition of $GS(R)$, where $V$ is the set of all nonzero simple ideals of $R$, and $W$ is the set of all non-simple ideals of $R$, is necessary and sufficient for $GS(R)$ to be bipartite. We prove this in the next corollary, but before we do that we need to draw the attention of the reader to the fact that if an ideal does not include any simple ideal, then it is an isolated vertex which can be freely added to any part of a bipartition of $GS(R)$. So, what maters when considering by partitions is the nonzero simple ideals and ideals containing anyone of them.

Corollary 44. Assume $GS(R)$ is not null. Then, $GS(R)$ is bipartite if and only if the $(V, W)$-bipartition of $GS(R)$ exists, where $V$ is the set of all nonzero simple ideals of $R$, and $W$ is the set of all non-simple ideals of $R$.

Proof. Assume $GS(R)$ is bipartite. Let $X$ and $Y$ be a bipartition. Since $GS(R)$ is not null, then $R$ contains at least one nonzero simple ideal. Without loss of generality, assume $R \in Y$. Since $R$ is adjacent to every nonzero simple ideal as Remark 22 states, then all nonzero simple ideals belong to $X$. Thus, all non-simple ideals containing simple ideals must belong to $Y$. The isolated vertices are distributed randomly to $X$ and $Y$. Now if we move all isolated vertices from $X$ to $Y$, the new bipartition is the $(V, W)$-bipartition with $V$ is $X$ after deleting the isolated vertices and $W$ is $Y$ plus all the isolated vertices. The proof of the converse is quite obvious.

Recall that an ideal $I$ of a ring $R$ is essential (or large) if $I \cap J \neq 0$, for every nonzero ideal $J$ of $R$. In what follows, when we assume $GS(R)$ is bipartite, we consider the $(V, W)$-bipartition.

Theorem 45. Assume $GS(R)$ is not null and bipartite. Then the following statements are equivalent:

(1) $GS(R)$ is complete bipartite.

(2) The intersection of all nonsimple ideals is $Soc(R)$.

(3) $Soc(R)$ is an essential ideal.

(4) $R$ is Artinian and $diam(GS(R)) \leq 2$.

(5) $GS(R)$ is path connected and $diam(GS(R)) \leq 2$.

Proof. The proof is easy when $R$ contains only one nonzero simple ideal because $GS(R)$ is a star graph and then (1) to (5) hold directly. Therefore, we assume that $GS(R)$ contains more than one nonzero simple ideal. By Corollary 44, there exists the $(V, W)$-bipartition consisting of the set $V$ of all nonzero simple ideals and the set $W$ consisting of all non-simple ideals.

$1 \Rightarrow 2:$ Suppose $GS(R)$ is complete bipartite. Then every non-simple ideal is adjacent to every simple ideal. Hence, every non-simple ideal contains the socle of $R$. Thus, $Soc(R)$ is included in the intersection of all non-simple ideals. Now, $Soc(R)$ is not simple and hence it includes the intersection of all non-simple ideals. At this point, we conclude that $Soc(R)$ is equal to the intersection of all non-simple ideals.

$2 \Rightarrow 3:$ The proof is trivial.

$3 \Rightarrow 4:$ Assume that $Soc(R)$ is an essential ideal of $R$. The proof that $R$ is Artinian is quite easy and well known in the literature. We only need to show that $diam(GS(R)) \leq 2$. By Lemma 30, the distance between any two nonzero simple ideals is $2$. Let $I \in V$ and $J \in W$. If $I \subsetneqq J$, then $I \leftrightarrow J$ and $d(I, J) = 1$. Assume now $I \nsubseteq J$. Since $Soc(R)$ is essential, then $Soc(R) \cap J \neq 0$, which means that $J$ contains a nonzero simple ideal $K \neq I$. Then $I \leftrightarrow I \oplus K \leftrightarrow J$ is a path between $I$ and $J$ of length $2$. Next, assume $I, J \in W$. We have $I \cap J$ is not simple. Since $Soc(R)$ is essential, the ideal $I \cap J$ contains a nonzero simple ideal $K$. Now the path $I \leftrightarrow K \leftrightarrow J$ between $I$ and $J$ has length $2$.

$4 \Rightarrow 5:$ Apply Theorem 31.

$5 \Rightarrow 1:$ Assume $GS(R)$ is path connected such that $diam(GS(R)) \leq 2$. Let $I \in V$ and $J \in W$. Then, there exists a path connecting $I$ and $J$. By assumption, the length of the shortest path connecting $I$ and $J$ equals $1$ or $2$. However, if the length of this shortest path is $2$, then we get a contradiction to the hypothesis that says "$GS(R)$ is bipartite". So, the length of this shortest path is $1$. That is, $I$ is adjacent to $J$. This completes the proof.

As an outcome of Theorem 45, if $GS(R)$ is complete bipartite, then $GS(R) = K_{m, n} = K_{n, m}$, where $m = |V|$ and $n = |W|$.

6.   Cliques of $GS(R)$

In this part, we study the cliques of $GS(R)$ and identify the clique number.

Definition 46. Let $I$ be a nonzero simple ideal of $R$. We say that the nonzero ideals $J$ and $K$ are adjacent through $I$ if $J \cap K = I$.

Proposition 47. Every clique of $GS(R)$ contains at most one nonzero simple ideal.

Proof. The proof is straightforward from Remark 22.

It follows from Proposition 47 that there are two types of cliques in $GS(R)$. The first type of cliques contains no simple ideals, while the second type of cliques contains exactly one nonzero simple ideal. The next example exhibits these types of cliques.

Example 48. Let $R = I \oplus J \oplus K$ be a semisimple ring. Then, the subgraph $I \oplus J \leftrightarrow J \oplus K \leftrightarrow I \oplus K \leftrightarrow I \oplus J$ is a clique whose vertices are not simple ideals. However, the subgraph $I \oplus J \leftrightarrow I \leftrightarrow I \oplus K \leftrightarrow I \oplus J$ is a clique with one simple nonzero ideal as Proposition 47 emphasizes.

In the next work, we are going to study each type of cliques in order to discover the clique number of $GS(R)$. The next theorem states that a clique containing a unique nonzero simple ideal $I$ is a subgraph of $GS(R, I)$ whose vertices are adjacent through $I$.

Theorem 49. Let $\Lambda$ be a clique containing one nonzero simple ideal $I$. Then $\Lambda$ consists, beside the vertex $I$, vertices in $N(I)$ that are adjacent to each other through $I$.

Proof. Let $J$ and $K$ be two vertices in $\Lambda$. Then $J \cap K$ is nonzero simple. Since $I \leftrightarrow J$ and $I \leftrightarrow K$, we get $J, K \in N(I)$ and $I \subseteq J \cap K$. Thus, $I = J \cap K$. The converse is obvious.

Corollary 50. Let $\Lambda$ be a clique containing one nonzero simple ideal $I$. Then $|Ver[\Lambda]| > 2$ if and only if $R \notin Ver[\Lambda]$ and $Ver[\Lambda]$ has at least two proper non-simple ideals (that are adjacent through $I$).

Proof. Suppose $Ver[\Lambda]$ contains at least $3$ vertices. Since $I$ must be among the vertices of $\Lambda$, by Theorem 49, the other vertices are non-simple ideals that are adjacent to each other through $I$. By Remark 22, neither of the non-simple vertices equals $R$. The converse is trivial.

Definition 51. Let $I$ be a nonzero simple ideal of $R$. Then, the largest clique of $GS(R)$ containing $I$ is called the maximal clique induced by $I$.

Let $I$ be a nonzero simple ideal of $R$. Then the clique $I \leftrightarrow R$ is always a maximal clique induced by $I$, which we call the trivial maximal clique induced by $I$. It is not difficult to see from Corollary 50 that if $|N(I)| = 1$, then the trivial maximal clique induced by $I$ is the only maximal clique induced by $I$. However, if $|N(I)| > 1$, Then there is another maximal clique induced by $I$ which consists, in addition to $I$, of all proper non-simple ideals in $N(I)$ that are adjacent to each other through $I$. We denote this non-trivial maximal clique by $\Lambda(I)$. Notice that $|Ver[\Lambda(I)]| \geq 2$.

Example 52. In $GS(\mathbb{Z}_4)$, the maximal cliques induced by the ideal $2\mathbb{Z}_4$ are only the trivial maximal clique $2\mathbb{Z}_4 \leftrightarrow \mathbb{Z}_4$.

Example 53. In Example 48, $\Lambda(I)$ is $I \leftrightarrow I \oplus J \leftrightarrow I \oplus K \leftrightarrow I$. Therefore $|\Lambda(I)| = 3$.

In the next work we study the second type of cliques which does not contain nonzero simple ideals. The following definition will be handy.

Definition 54. Let $S$ be a nonempty set of nonzero simple ideals. By a clique of $GS(R)$ induced by $S$, we mean a clique of $GS(R)$ such that any two of its vertices are adjacent through a member of $S$, and every member of $S$ is the intersection of two vertices of this clique.

Example 55. In Example 48, the subgraph $\Lambda:I \oplus K \leftrightarrow I \oplus J \leftrightarrow J \oplus K \leftrightarrow I \oplus K$ is the unique clique induced by $S = \{I, J, K\}$. However, the subgraphs $\Lambda_1:I \leftrightarrow R$, $\Lambda_2:I \oplus K \leftrightarrow I$, $\Lambda_3:I \leftrightarrow I \oplus K \leftrightarrow I \oplus J \leftrightarrow I$ are some cliques induced by $S = \{I\}$. On the other hand, there is no clique in $GS(R)$ induced by $S = \{I, J\}$.

As displayed in the previous example, the set of all cliques induced by a nonempty set $S$ of nonzero simple ideals may be empty, singleton, or contain more than one clique.

Remark 56. If $S$ contains at least two nonzero simple ideals, then all vertices of a clique induced by $S$ are non-simple ideals. We leave it to the reader to check out that the last statement is true.

Next, we show that if a nonempty set $S$ of nonzero simple ideals induces cliques, then there is a maximum clique induced by $S$, i.e., a clique induced by $S$ that is not a subgraph of another clique induced by $S$.

Theorem 57. Let $S$ be a nonempty set of nonzero simple ideals of $R$ which induces cliques in $GS(R)$. Then there is a maximal clique induced by $S$.

Proof. Let $\mathcal{L}$ be the set of all cliques induced by $S$. By hypothesis, $\mathcal{L} \neq \emptyset$. Let $\Lambda_1 \subseteq \Lambda_2 \subseteq \ldots$ be a chain of members of $\mathcal{L}$. Then $\bigcup\limits_{n = 1}^{\infty} \Lambda_n$, the union of the graphs $\Lambda_1, \Lambda_2, \ldots$, is a member of $\mathcal{L}$ and it is an upper bound of the chain. By Zorn's Lemma, $\mathcal{L}$ has a maximal element.

Notation 58. A maximal clique of $GS(R)$ induced by a nonempty set $S$ of nonzero simple ideals of $R$ is denoted by $\Lambda(S)$.

If $S = \{I\}$, where $I$ is a nonzero simple ideal of $R$, then either $\Lambda(S)$ is the trivial maximal clique $R \leftrightarrow I$ or $\Lambda(S) = \Lambda(I)$. In general, a maximal clique of $GS(R)$ induced by $S$ is not necessarily unique, as we shall see in the next example.

Example 59. In Example 48, there is a unique maximal clique induced by $S = \{I, J, K\}$ given by $\Lambda(S):I \oplus K \leftrightarrow I \oplus J \leftrightarrow J \oplus K \leftrightarrow I \oplus K$. Also, $\Lambda_1:I \leftrightarrow R$, and $\Lambda_3:I \leftrightarrow I \oplus K \leftrightarrow I \oplus J \leftrightarrow I$ are two maximal cliques induced by $S = \{I\}$. Notice that $\Lambda_2:I \oplus K \leftrightarrow I$ is not a maximal clique induced by $S = \{I\}$ in $GS(R)$ since it is a subgraph of $\Lambda_3$.

Theorem 60. If $\Lambda$ is a clique of $GS(R)$, then there is a unique nonempty set $S$ of nonzero simple ideals of $R$ inducing $\Lambda$.

Proof. Suppose $\Lambda$ is a clique of $GS(R)$. Let $S$ be the set of all possible intersections of the vertices of $\Lambda$. Then $\Lambda$ is induced by $S$. The uniqueness of $S$ follows from Definition 54.

Remark 61. In $GS(R)$, the following statements are true:

(1) $\omega(GS(R))$ equals the supremum of the set

(2) $\omega(GS(R)) \geq 2$.

(3) If the order of $GS(R)$ is finite, then $2 \leq \omega(GS(R)) \leq |Ver[GS(R)]|$.

Example 62. We have

(1) $\omega(GS(\mathbb{Z}_4)) = 2$.

(2) Let $R$ be a semisimple ring with $2$ components. A direct analysis leads to that $\omega(GS(R)) = 2$.

(3) Let $R$ be a semisimple ring with $3$ components. A direct analysis leads to that $\omega(GS(R)) = 3$.

(4) Consider $R = \mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \mathbb{Z}_2$, a semisimple ring with $4$ components. Let $I = \mathbb{Z}_2 \oplus 0 \oplus 0 \oplus 0$. Then $Ver[\Lambda (I)] = \{I, \mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus 0 \oplus 0, \mathbb{Z}_2 \oplus 0 \oplus \mathbb{Z}_2 \oplus 0, \mathbb{Z}_2 \oplus 0 \oplus 0 \oplus \mathbb{Z}_2 \}$. Thus, $4 \leq \omega(GS(R))\leq 15$, where $15$ is the order of $GS(R)$ which is equal to the number of nonzero ideals of $R$. As a matter of fact, taking all possible cliques of $R$, it can be shown that the maximal clique with the largest number of vertices has an order of $4$. That is $\omega(GS(R)) = 4$.

(5) Let $R = \mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \ldots$ be a semisimple ring with infinitely many components. For every $n \in \mathbb{N}$, let $I_n = 0 \oplus 0 \oplus \ldots \oplus \mathbb{Z}_2 \oplus 0 \oplus \ldots$, where $\mathbb{Z}_2$ is located in the component number $n$. Then $Ver[\Lambda (I_1)] = \{I_1, I_1\oplus I_2, I_1\oplus I_3, \ldots\}$. Thus, $\omega(GS(R)) = \infty$.

7.   Dominating sets and domination number of $GS(R)$

In this section, we consider the dominating sets of $GS(R)$, and give a formula which help compute the domination number of $GS(R)$.

Definition 63. A dominating set $X$ is non-shrinkable, if removing a vertex from $X$ makes $X$ a non-dominating set.

Theorem 64. Let $D$ be the set consisting of all nonzero simple ideals of $R$ and all non-simple ideals empty of nonzero simple ideals. Then $D$ is a non-shrinkable dominating set of $GS(R)$.

Proof. Let $J$ be vertex not in $D$, then $J$ contains a nonzero simple ideal $I$. Now $J \leftrightarrow I$.

Corollary 65. Let $D$ be the set consisting of all nonzero simple ideals of $R$ and all non-simple ideals empty of nonzero simple ideals. Then

(1) $\gamma(GS(R)) \leq |D|$.

(2) If $GS(R)$ is connected, then $D$ consists only of nonzero simple ideals.

Proof. The proof is easy.

Notice that $D$ is not the only type of dominating sets of $GS(R)$. However, we shall show, in the next work, that every dominating set can be reduced to a non-shrinkable set whose vertices are the isolated vertices of $GS(R)$ along with some semisimple ideals. Before we do that, we need the following notation.

Notation 66. Let $B$ be a dominating set of $GS(R)$. Denote b $\widetilde B$ the set consisting of the following vertices:

(1) all non-simple ideals empty of nonzero simple ideals,

(2) $Soc(V)$ for each $V \in B$, and

(3) $V$ for each $V \in B$ such that $V\neq Soc(V)$ and $Soc(V) \in B$.

Lemma 67. If $B$ is a dominating set of $GS(R)$, then $\widetilde{B}$ is also a dominating set such that $|\widetilde{B}| \leq |B|$.

Proof. Assume $B$ is a dominating set of $GS(R)$. Then $B$ contains all non-simple ideals empty of nonzero simple ideals. Let $V$ be a non isolated vertex of $GS(R)$. We study different cases. In the first case, assume that $V \notin B$. Then $V \leftrightarrow I$, where $I \in B$. Thus, $V \leftrightarrow Soc(I)$. In the second case, assume that $V \in B$. If $V = Soc(V)$, then $V \in \widetilde B$. However, if $V \neq Soc(V)$ and $Soc(V) \in B$, then by (3) in Notation 66, we have $V \in \widetilde B$. Finally, if $V \neq Soc(V)$, $Soc(V) \notin B$, and $Soc(V)$ is simple, then $V \leftrightarrow Soc(V)$. However, if $V \neq Soc(V)$, $Soc(V) \notin B$, and $Soc(V)$ is not simple. Since $B$ is a dominating set, there exists $J \in B$ such that $Soc(V) \leftrightarrow J$ which implies $Soc(V) \leftrightarrow Soc(J)$ which in turn implies $V \leftrightarrow Soc(J)$. From the discussion above, we conclude that $\widetilde{B}$ is a dominating set. Now, define the function $f: B \to \widetilde{B}$ by

Then $f$ is an onto function. Therefore, $|\widetilde{B}| \leq |B|$.

Lemma 68. Assume $R$ is not simple and $B$ a non-shrinkable dominating set of $GS(R)$. Then $GS(R)$ does not contain $R$ and $Soc(R)$ simultaneously, unless $R$ is semisimple. Moreover, if $R \notin B$, then $B$ contains a nonzero simple ideal.

Proof. Suppose $R \neq Soc(R)$. Then $R$ and $Soc(R)$ cannot be inside $B$ at the same time, otherwise $B$ is shrinkable and this is a contradiction. The rest is trivial.

Notice that $\widetilde B$ may be shrinkable as indicated in the following example.

Example 69. Let $R = I \oplus J$ be a semisimple ring. Consider the dominating sets $B_1 = \{I, R\}$ and $B_2 = \{I, J\}$. We have $\widetilde B_1 = B_1$ and $\widetilde B_2 = B_2$. Also, $B_1$ is shrinkable to $\{R\}$ while $B_2$ is not shrinkable.

Remark 70. In $GS(R)$, if $V \leftrightarrow U$, then $V \leftrightarrow Soc(U)$, $Soc(V) \leftrightarrow U$, and $Soc(V) \leftrightarrow Soc(U)$. Conversely, If $Soc(V) \leftrightarrow Soc(U)$, then $V \leftrightarrow Soc(U)$ and $Soc(V) \leftrightarrow U$, but it's not necessary that $V \leftrightarrow U$. To see this, Let $R = \mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \mathbb{Z} \oplus \mathbb{Z}$, $V = \mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \mathbb{Z} \oplus 0$ and $U = \mathbb{Z}_2 \oplus 0 \oplus \mathbb{Z} \oplus \mathbb{Z}$. We have $Soc(V) = \mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus 0 \oplus 0$ is adjacent to $Soc(U) = \mathbb{Z}_2 \oplus 0 \oplus 0 \oplus 0$ in $GS(R)$, but $V$ is not adjacent to $U$ because $V \cap U = \mathbb{Z}_2 \oplus 0 \oplus \mathbb{Z} \oplus 0$ which is not simple. Also, if $V \leftrightarrow Soc(U)$, then it's not necessary that $V \leftrightarrow U$ as shown in the same example.

In the next theorem, we show that any dominating set can be replaced with a non-shrinkable dominating set whose elements are semisimple ideals of $R$.

Theorem 71. Let $B$ a dominating set of $GS(R)$. Then, there exists a non-shrinkable dominating set $Y$ such that $|Y| \leq |B|$ and $Y$ consists, in addition to the isolated vertices, of semisimple ideals of $R$. Moreover, If $R$ is not semisimple, then $Y$ contains at least one nonzero simple ideal.

Proof. By Lemma 67, we can replace $B$ with $\widetilde B$. We have $|\widetilde B| \leq |B|$ and all elements of $\widetilde B$ are semisimple except perhaps for $V \in B$ such that $V \neq Soc(V)$ and $Soc(V) \in B$. We know that according to Notation 66, such $V$ and $Soc(V)$ are elements in $\widetilde B$. Now, we replace such $V$ with any nonzero simple ideal (we denote it by $T_V$) contained in $V$. We call the new set $B_{\circ}$. It's easy to see that $B_{\circ}$ consists of only semisimple ideals and $|B_{\circ}| \leq |\widetilde B| \leq |B|$. To demonstrate that $B_{\circ}$ is a dominating set, let $U$ be a vertex not in $B_{\circ}$. If $U \notin \widetilde B$, then $U$ is adjacent to some vertex $V\in \widetilde B$. We need only to worry about the case when $V \neq Soc(V)$ and both $V, Soc(V)\in B$. By Remark 70, $U \leftrightarrow Soc(V)$ and $Soc(V) \in B_{\circ}$. Next, assume $U \in \widetilde B$. Again, we need only to worry about the case when $U \neq Soc(U)$ and both $U, Soc(U)\in B$. By the definition of $B_{\circ}$, we get that $U \leftrightarrow T_U$ and $T_U \in B_{\circ}$. From the previous argument we obtain that $B_{\circ}$ is a dominating set. Since $B_{\circ}$ may be shrinkable, then $B_{\circ}$ contains a non-shrinkable dominating set $Y$. The rest follows from Lemma 68.

The proof of the next corollary is direct from Theorem 71.

Corollary 72. If $R$ is semisimple, then

If $R$ is not semisimple, then

Example 73. Let $R = I \oplus J$ be a semisimple ring. Then $Y = \{R\}$ is a non-shrinkable dominating set of $GS(R):I \leftrightarrow R \leftrightarrow J$ with the least cardinality. Thus, $\gamma(GS(R)) = 1$.

Example 74. Let $R = I \oplus J \oplus K$ be semisimple ring. Then $Y = \{I \oplus J, K\}$ is a non-shrinkable dominating set of $GS(R)$ with the least cardinality. Thus, $\gamma(GS(R)) = 2$.

Example 75. Consider the ring $R = \mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \mathbb{Z} \oplus \mathbb{Z}$. Then $Y = \{0 \oplus 0 \oplus 0 \oplus \mathbb{Z}, 0 \oplus 0 \oplus \mathbb{Z} \oplus 0, \mathbb{Z}_2 \oplus 0 \oplus 0 \oplus 0, 0 \oplus \mathbb{Z}_2 \oplus 0 \oplus 0\}$ is a non-shrinkable dominating set of $GS(R)$ with the least cardinality. Thus, $\gamma(GS(R)) = 4$.

8.   Conclusions

The association of a graph to an algebraic structure has attracted many authors to study the interplay between the graph theoretic properties and the algebraic properties of the underlined algebraic structure. In this article, we defined the simple-intersection graph $GS(R)$ of a ring $R$ with unity. Then we studied the interplay between the algebraic properties of $R$, and the graph properties of $GS(R)$ such as connectedness, bipartiteness, girth and dominating sets.

Moreover, we determined precisely the girth, the domination number and the diameter of $GS(R)$. Furthermore, we developed a formula to compute the clique number of $GS(R)$.

Our results are interesting since they can be used to solve some coloring and optimization problems as well as develop more properties of $GS(R)$.

Conflict of interest

The authors declare no conflict of interest.