ABSTRACT

Let R be a commutative ring with non-zero identity. The cozero-divisor graph of R, denoted by, is a graph with vertices in, which is the set of all non-zero and non-unit elements of R, and two distinct vertices a and b in are adjacent if and only if and. In this paper, we investigate some combinatorial properties of the cozero-divisor graphs and such as connectivity, diameter, girth, clique numbers and planarity. We also study the cozero-divisor graphs of the direct products of two arbitrary commutative rings.

1. Introduction

Let R be a commutative ring with non-zero identity and let be the set of zero-divisors of R. For an arbitrary subset A of R, we put. The zero-divisor graph of R, denoted by, is an undirected graph whose vertices are elements of with two distinct vertices a and b are adjacent if and only if ab = 0.

The concept of zero-divisor graph of a commutative ring was introduced by Beck [1], but this work was mostly concerned with colorings of rings. The above definition first appeared in Anderson and Livingston [2], which contained several fundamental results concerning the graph. The zero-divisor graphs of commutative rings have been studied by several authors. For instance, the preservation and lack thereof of basic properties of under extensions to rings of polynomials and power series was studied by Axtell, Coykendall and Stickles in [3] and Lucas in [4]. Also Axtell, Stickles and Warfel in [5], considered the zero-divisor graphs of direct products of commutative rings.

Let be the set of all non-unit elements of R. For an arbitrary commutative ring R, the cozero-divisor graph of R, denoted by, was introduced in [6], which is a dual of zero-divisor graph “in some sense”. The vertex-set of is and for two distinct vertices a and b in, a is adjacent to b if and only if and, where cR is an ideal generated by the element c in R. Some basic results on the structure of this graph and the relations between two graphs and were studied in [6].

In this paper, we study the cozero-divisor graphs of the rings of polynomials, power series and the direct product of two arbitrary commutative rings. Also, we look at the preservation of the diameter and girth of the cozero-divisor graphs in some extension rings. Our results “in some sense” are the dual of the main results of [3-5].

Throughout the paper, R is a commutative ring with non-zero identity. We denote the set of maximal ideals and the Jacobson radical of R by and, respectively. Also, is the set of all unit elements of R. By a local ring, we mean a (not necessarily Noetherian) ring with a unique maximal ideal.

In a graph G, the distance between two distinct vertices a and b, denoted by, is the length of the shortest path connecting a and b, if such a path exists; otherwise, we set. The diameter of a graph G is

The girth of G, denoted by, is the length of the shortest cycle in G, if G contains a cycle; otherwise,. Also, for two distinct vertices a and b in G, the notation means that a and b are adjacent. A graph G is said to be connected if there exists a path between any two distinct vertices, and it is complete if it is connected with diameter one. We use to denote the complete graph with n vertices. Moreover, we say that G is totally disconnected if no two vertices of G are adjacent. For a graph G, let denote the chromatic number of the graph G, i.e., the minimal number of colors which can be assigned to the vertices of G in such a way that any two adjacent vertices have different colors. A clique of a graph is any complete subgraph of the graph and the number of vertices in a largest clique of G, denoted by, is called the clique number of G. Obviously (cf. see [7, p. 289]). For a positive integer r, an r-partite graph is one whose vertex-set can be partitioned into r subsets so that no edge has both ends in any one subset. A complete r-partite graph is one in which each vertex is joined to every vertex that is not in the same subset. The complete bipartite graph (2-partite graph) with subsets containing m and n vertices, respectively, is denoted by. A graph is said to be planar if it can be drawn in the plane so that its edges intersect only at their ends. A subdivision of a graph is any graph that can be obtained from the original graph by replacing edges by paths. A remarkable simple characterization of the planar graphs was given by Kuratowski in 1930. Kuratowski’s Theorem says that a graph is planar if and only if it contains no subdivision of or (cf. [8, p. 153]). Also, the valency of a vertex a is the number of edges of the graph G incident with a.

2. Cozero-Divisor Graph of

In this section, we are going to study some basic properties of the cozero-divisor graph of the polynomial ring. To this end, we first gather together the wellknown properties of the polynomial ring, which are needed in this section.

Remarks 2.1 Let be an arbitrary element in. Then we have the following statements:

• is a unit in if and only if a₀ is a unit and the coefficients are nilpotent elements of R.

• is nilpotent if and only if the coefficients are nilpotent.

• , where is the nilradical of.

• Since the polynomials x and 1 + x are non-units, is a non-local ring.

• By part (i), it is easy to see that is an induced subgraph of.

In the following theorem, we show that is always connected and its diameter is not exceeding three.

Theorem 2.2 The graph is connected and.

Proof. Since is a non-local ring, by [1, Theorem 2.5], it is enough to show that, for every non-zero element, there exist and such that. Now, assume that is a non-zero polynomial in of degree t. Since x is a non-unit element in, there exists a maximal ideal m of such that. So. On the other hand, by parts (ii) and (iii) of Remarks 2.1,. Also . Hence the graph is connected and.

The following proposition states that the diameter of is never one.

Proposition 2.3 The graph is never complete.

Proof. Clearly and. The claim now follows from [1, Theorem 2.1].

The following corollary is an immediate consequence of Theorem 2.2 and Proposition 2.3.

Corollary 2.4 or 3.

Proposition 2.5 Suppose that. Then

. In particular, if R is reduced, then

.

Proof. In view of [1, Corollary 2.4],

. Now, by Proposition 2.3, one can conclude that. Also, if R is reduced, then by Remarks 2.1 (ii), and so, by Remarks 2.1 (iii),.

In the next two theorems, we investigate the girth of the graph.

Theorem 2.6 Suppose that R is a non-reduced ring. Then every element of is in a cycle of length three.

Proof. Assume that is a non-zero element in of degree n and consider the elements and in, where. Then, by Remarks 2.1 (iv), there exist maximal ideals m₁ and m₂ of such that and. Since t > n, and. Also, by parts (ii) and (iii) of Remarks 2.1, and do not belong to. So, and

. Thus, is adjacent to both distinct vertices and. Moreover, it is easy to see that is adjacent to. Therefore we have the cycle

Theorem 2.7.

Proof. Consider the elements and in. So there exist two maximal ideals m₁ and m₂ in such that and. Hence the vertex is adjacent to. Also, clearly and. Now, since the polynomials x and do not divide the polynomial, we have that and. Hence

is the required cycle.

In the next theorem we study the clique number of.

Theorem 2.8 In the graph,

is infinity and hence the chromatic number is infinity.

Proof. Let be a positive integer and consider the subgraph of with vertex-set

. Now, for every two distinct polynomials and with i < j, clearly we have that

Also, since, we have that. This means that, and so does not divide the polynomial. Thus

. Hence, is a complete subgraph of which is isomorphic to

. So is infinity. This implies that

is infinity.

Theorem 2.9 The cozero-divisor graph is not planar.

Proof. In view of the proof of Theorem 2.8, for all positive integers, the cozero-divisor graph has a complete subgraph isomorphic to. In particular, for, the graph is a subgraph of. So, by Kuratowski’s Theorem (cf. [8, p. 153]), is not planar.

Recall that a graph on n vertices such that of the vertices have valency one, all of which are adjacent only to the remaining vertex a, is called a star graph with center a. Also, a refinement of a graph H is a graph G such that the vertex-sets of G and H are the same and every edge in H is an edge in G. Now, we have the following result.

Proposition 2.10 If there exists a maximal ideal m of R with, then there is a refinement of a star graph in the structure of.

Proof. Suppose that is a maximal ideal of R. Then, for every element with, we have that. Also. Hence, a is adjacent to b. Therefore, is a refinement of a star graph with center a. Now, by Remarks 2.1 (v), is an induced subgraph of. So contains a refinement of a star graph.

3. Cozero-Divisor Graph of

We begin this section with some elementary remarks about the rings of power series which may be valuable in turn. These facts can be immediately gained from the elementary notes about power series.

• Remarks 3.1

• is a unit in if and only if is a unit in R.

• belongs to the Jacobson radical of if and only if belongs to the Jacobson radical of R.

• is a local ring if and only if is local.

• The cozero-divisor graph is an induced subgraph of, but is not a subgraph of, since 1 + x is a vertex of but it is not in the vertex-set of.

In the following proposition, we study the connectivity and diameter of, whenever R is non-local.

Proposition 3.2 Let R be a non-local ring. Then the cozero-divisor graph is connected and

.

Proof. Suppose that is a non-zero element in. By [6, Theorem 2.5], it is enough to show that is adjacent to some element in. In this regard, we have the following two cases:

Case 1. Assume that, for some and consider an element b in. We will show that is adjacent to b. Clearly, by Remarks 3.1 (i)(ii),. Now, assume in contrary that and look for a contradiction.

We have that, for some in. Since, by Remarks 3.1 (ii), , we have that which is impossible. Also, if , then, for some non-zero element g_i in R, which is impossible. Therefore and b are adjacent.

Case 2. Suppose that, for all. First assume that, for some. Hence, there exist maximal ideals m and such that. By considering an element b in, one can conclude that a_i is adjacent to b. Now if, then, for some non-zero element g_i in R which is a contradiction because the vertices a_i and b are adjacent. On the other hand,. Thus the vertices and b are adjacent.

Now, let, for all. Choose . Hence. We claim that is adjacent to, where t is the least non-zero power of in the polynomial. Clearly,. Now, if for some in, then

which belongs to and this is impossible. Hence, we have that is adjacent to.

Therefore is connected and also, by considering the above cases, it is routine to check that.

In the next lemma, we investigate the adjacency in in the case that R is a local ring.

Lemma 3.3 Assume that R is a local ring with maximal ideal m. Let be a non-zero element in. Then we have the following statements:

• if, then is adjacent to;

• if and, for some, then is adjacent to all non-zero elements of; and• if and, for all, then is adjacent to, where is the least non-zero power of in.

Proof. 1) Assume on the contrary that, where. Then and . Since a₀ and g₀ belong to m, we have that which is a contradiction. Also we have that. Thus is adjacent to x.

2) Let b be a non-zero element in m. Then if, we conclude that which is impossible. So. Now, since . Therefore, is adjacent to.

3) Clearly, since is the least non-zero power of in,. Moreover, if , for some in, then

This means that which is impossible. Hence. So is adjacent to.

The following result, which is one of our main results in this section, states that is connected and the diameter of is not exceeding four.

Theorem 3.4 The cozero-divisor graph

is always connected and also.

Proof. Owing to Proposition 3.2, the result holds in the case that R is non-local. Assume that R is a local ring with maximal ideal m. In view of part (iii) of Remarks 3.1, is also a local ring. Now, let and be two non-zero elements in that are not adjacent. We have the following cases for consideration:

Case 1. and. Then by Lemma 3.3 (i), we have that.

Case 2.. If, for some i, j, then by part (ii) of Lemma 3.3, , for all non-zero elements in.

Also, if, for all, and are the least non-zero powers of x in and, respectively, with, then by Lemma 3.3 (iii), one can easily check that.

Finally, we may assume that for some positive integer i, and, for all j. Thus, by parts (ii) and (iii) of Lemma 3.3, we have the path , where c is a non-zero element in and is the least non-zero power of x in.

Case 3. Without loss of generality, we may assume that and. So, if, for some j, then in view of parts (i) and (ii) of Lemma 3.3, we have the path, where is a non-zero element in m.

Moreover, if, for all j, then by Lemma 3.3, we have, where is a non-zero element in m and t is the least non-zero power of in.

Therefore, the cozero-divisor graph is connected and in view of the above cases, one can easily check that.

The following lemma is needed in the sequel.

Lemma 3.5 Let and let i and j be positive integers such that. Then the vertices and are adjacent in.

Proof. Suppose to the contrary that , where is a non-zero polynomial in. So, we have and b₀ = 0. Thus a = 0 which is a contradiction. Hence. Also, clearly. So the vertices and are adjacent in the cozero-divisor graph.

In the next theorem, we show that.

Theorem 3.6 The cozero-divisor graph has girth three.

Proof. Let. Consider the elements x, and in. Clearly,

and. Also, since

, and don’t belong to. Hence, we have the following path

Now, in view of Lemma 3.5, one can conclude that and are adjacent. Therefore, we have the cycle. Hence,

.

In the next theorem, we compute the clique number of.

Theorem 3.7 In the graph,

is infinity and hence is also infinity.

Proof. For every positive integer, it is enough to construct a complete subgraph of with vertices. To this end, let be an arbitrary positive integer and. Then, by Lemma 3.5, it is easy to see that the subgraph with vertex-set

is a complete subgraph of

which is isomorphic to. So

is infinity and this implies that is infinity.

We end this section with the following theorem.

Theorem 3.8 The cozero-divisor graph is not planar.

Proof. In view of the proof of Theorem 3.7, is a subgraph of. Thus, by Kuratowski’s Theorem, is not planar.

4. Cozero-Divisor Graph of

Throughout this section, R₁ and R₂ are two commutative rings with non-zero identities. We will study the cozerodivisor graph of the direct product of R₁ and R₂. Note that an element belongs to if and only if or. We begin this section with the following lemma.

Lemma 4.1 Suppose that is a direct product of finite commutative rings. If is adjacent to in, for some, then every element in R with i-th component is adjacent to all elements in R with i-th component.

Proof. Suppose that is adjacent to in and assume on the contrary that the vertices and are not adjacent in. Without loss of generality, suppose that

. Thus

, for some non-zero element. Therefore and hence is not adjacent to, which is a contradiction.

The following corollary follows immediately from Lemma 4.1.

Corollary 4.2 Suppose that,

such that they are not adjacent in. Then a is not adjacent to in and b is not adjacent to in.

In the next lemma, we establish some relations between the adjacency in the graph and adjacency in both graphs and.

• Lemma 4.3

• Let and. Then is adjacent to in if and only if b is adjacent to in.

• Let and. Then is adjacent to in if and only if is adjacent to in.

Proof. 1) Suppose that is adjacent to. Note that if at least one of the elements or is zero or unit, then is not adjacent to in. Thus we can suppose that. Now, if is not adjacent to, then or. So without loss of generality, we may assume that for some non-zero element. Hence. This means that and are not adjacent in which is impossible. Therefore and are adjacent in. Conversely, if is adjacent to, then by Lemma 4.1, we have that is adjacent to.

2) The proof is similar to part 1).

The following propositions follow directly from Lemma 4.3.

Proposition 4.4 Assume that either or is not planar. Then is not planar.

Proof. Without loss of generality, suppose that is not planar. So, by Kuratowski’s Theorem (cf. [8, p. 153]), it contains a subdivision of or. Now, by Lemma 4.3 (ii), one can conclude that is not planar.

Proposition 4.5 In, we have the following inequalities:

;

• .

Remark 4.6 Suppose that and. Then is adjacent to.

In the following theorem, we invoke the previous lemmas to show that is a complete bipartite graph whenever and are fields.

Theorem 4.7 Assume that and are fields. Then is a complete bipartite graph.

Proof. Put and

. Clearly. By Remark 4.6, every element in V₁ is adjacent to all elements of V₂ and vice versa. Also, it is easy to see that there is no adjacency between vertices in V₁ (or V₂). So is a complete bipartite graph.

Corollary 4.8 Let be an arbitrary field. Then and are star graphs.

Remark 4.9 It is easy to see that is adjacent to in, for any, and. Similarly, is adjacent to , for any, and .

The following theorem is one of our main results in this section.

Theorem 4.10 The cozero-divisor graph is connected and.

Proof. Suppose that and are arbitrary elements in. We have the following cases for consideration:

Case 1.. If, then consider the path. If and, then, by Remark 4.9, we have that. Now, suppose that and. Then, in view of Remarks 4.6 and 4.9, one can obtain the path in. The similar result holds in the case that and.

Case 2. and. If, then, by Remark 4.9, whenever, we have that . Otherwise,. Since and, we have. Now, if , then. But and this implies that which is not true. Hence. Also, since, it is easy to see that. Therefore, we have the path. Also, if, then by Remarks 4.6 and 4.9, we can consider the path. The similar result holds if and.

Case 3.. Then we have that , and we can apply Case 1 on the second component of ordered pairs.

Now, in view of the above cases, it is easy to see that.

In the next proposition, we provide a characterization of the complete cozero-divisor graph.

Proposition 4.11 The graph is complete if and only if is isomorphic to.

Proof. If, then is not adjacent to, for some. Similarly, if, then is not complete. So, if is complete, then. Also, clearly the graph is complete.

Corollary 4.12 If, then or 3.

In the following theorem, we study the girth of . Note that we consider to be totally disconnected.

• Theorem 4.13

• If at least one of the cozero-divisor graph or is not totally disconnected, then .

• If and, then.

• If and R₂ is a field, then.

• If and R₂ is not a field, then or.

Proof. 1) Without loss of generality, suppose that such that a is adjacent to b. Now, by Lemma 4.3 (i) and Remark 4.9, we have the cycle in.

2) Let and such that a and b are not identity. Now, consider the cycle

in.

3) By Corollary 4.8, is a star graph and so.

4) First, assume that. Let and. Now, by Remarks 4.6 and 4.9, we have the cycle in. In the case that, if is not totally disconnected, then by part 1), . So, assume that there is no adjacency in. In this situation, we first show that is a bipartite graph. To this end, set

and. Clearly,

. Also, by Lemma 4.3, no two vertices in (or) are adjacent. So is a bipartite graph, and thus or. Now, by Remark 4.9, is adjacent to all vertices in, where, and also is adjacent to all vertices in, where. Hence, if there exist an element and such that is adjacent to in, then. Otherwise, the girth of the cozero-divisor graph is infinity.

The following example presents a ring with which satisfies parts 1) and 4) of Theorem 4.13. This shows that all cases in the proof of the last part of Theorem 4.13, can occur.

Example 4.14 Let and. Then and by Proposition 4.11, is complete. Hence, by Theorem 4.13 (i), we have that.

5. Acknowledgements

The authors are deeply grateful to the referee for careful reading of the manuscript and helpful suggestions.

REFERENCES

NOTES

^*Corresponding author.