Article Search
eISSN 0454-8124
pISSN 1225-6951

### Article

Kyungpook Mathematical Journal 2020; 60(4): 723-729

Published online December 31, 2020

### The Zero-divisor Graph of $ℤ n [ X ]]$

Min Ji Park, Eun Sup Kim, Jung Wook Lim*

Department of Mathematics, College of Life Science and Nano Technology, Hannam University, Daejeon 34430, Republic of Korea
e-mail : mjpark5764@gmail.com
Department of Mathematics, College of Natural Sciences, Kyungpook National University, Daegu 41566, Republic of Korea
e-mail : eskim@knu.ac.kr
Department of Mathematics, College of Natural Sciences, Kyungpook National University, Daegu 41566, Republic of Korea
e-mail : jwlim@knu.ac.kr

Received: June 13, 2020; Revised: July 28, 2020; Accepted: August 4, 2020

Let $ℤ n$ be the ring of integers modulo n and let $ℤ n [ X ] ​ ]$ be either $ℤ n [ X ]$ or $ℤ n [ ​ [ X ] ​ ]$ . Let $Γ ( ℤ n [ X ] ​ ] )$ be the zero-divisor graph of $ℤ n [ X ] ​ ]$ . In this paper, we study some properties of $Γ ( ℤ n [ X ] ​ ] )$ . More precisely, we completely characterize the diameter and the girth of $Γ ( ℤ n [ X ] ​ ] )$ . We also calculate the chromatic number of $Γ ( ℤ n [ X ]] )$ .

Keywords: Γ(ℤ,n[X)⟧,, diameter, girth, clique, chromatic number

### 1.1. Preliminaries

In this subsection, we review some concepts from basic graph theory. Let G be a (undirected) graph. Recall that G is connected if there exists a path between any two distinct vertices of G. The graph G is complete if any two distinct vertices are adjacent. The complete graph with n vertices is denoted by Kn. The graph G is a complete bipartite graph if G can be partitioned into two disjoint nonempty vertex sets A and B such that two distinct vertices are adjacent if and only if they are in distinct vertex sets. For vertices a and b in G, d(a, b) denotes the length of the shortest path from a to b. If there is no such path, then d(a, b) is defined to be ∞; and d(a, a) is defined to be zero. The diameter of G, denoted by diam(G), is the supremum of {d(a, b) | a and b are vertices of G}. The girth of G, denoted by g(G), is defined as the length of the shortest cycle in G. If G contains no cycles, then g(G) is defined to be ∞. A subgraph H of G is an induced subgraph of G if two vertices of H are adjacent in H if and only if they are adjacent in G. The chromatic number of G is the minimum number of colors needed to color the vertices of G so that no two adjacent vertices share the same color, and is denoted by χ(G). A clique C in G is a subset of the vertex set of G such that the induced subgraph of G by C is a complete graph. A maximal clique in G is a clique that cannot be extended by including one more adjacent vertex. The clique number of G, denoted by cl(G), is the greatest integer $n≥1$ such that $Kn⊆G$. If $Kn⊆G$ for all integers $n≥1$, then cl(G) is defined to be ∞. It is easy to see that $χ(G)≥cl(G)$.

### 1.2. The Zero-divisor Graph of a Commutative Ring

Let R be a commutative ring with identity and Z(R) the set of nonzero zero-divisors of R. The zero-divisor graph of R, denoted by Γ(R), is the simple graph with the vertex set Z(R), and for distinct a, b ∈ Z(R), a and b are adjacent if and only if ab=0. Clearly, Γ(R) is the null graph if and only if R is an integral domain.

In [6], Beck first introduced the concept of the zero-divisor graph of a commutative ring and in [3], Anderson and Naseer continued to study. In [3] and [6], all elements of R are vertices of the graph and the authors were mainly interested in graph coloring. In [2], Anderson and Livingston gave the present definition of Γ(R) in order to emphasize the study of the interplay between graph-theoretic properties of Γ(R) and ring-theoretic properties of R. It was shown that Γ(R) is connected with diam(Γ(R)) ≤ 3 [2,Theorem 2.3]. In [8,(1.4)], Mulay proved that g(Γ(R)) ≤ 4. In [5], the authors studied the zero-divisor graphs of polynomial rings and power series rings.

For more on the zero-divisor graph of a commutative ring, the readers can refer to a survey article [1].

Let $ℤn$ be the ring of integers modulo n and let $ℤn[X]$ (resp., $ℤn[​[X]​]$) be the polynomial ring (resp., power series ring) over $ℤn$. Let $ℤn[X]​]$ be either $ℤn[X]$ or $ℤn[​[X]​]$. In [9], the authors studied the zero-divisor graph of $ℤn$. In fact, they completely characterized the diameter, the girth and the chromatic number of $Γ(ℤn)$. The purpose of this paper is to study some properties of the zero-divisor graph of $ℤn[X]​]$. If n is a prime number, then $ℤn[X]​]$ has no zero-divisors; so $Γ(ℤn[X]​])$ is the null graph. Hence in this paper, we only consider the case that n is a composite. In Section 2, we completely characterize the diameter and the girth of $Γ(ℤn[X]​])$. In Section 3, we calculate the chromatic number of $Γ(ℤn[X]​])$. Note that all figures are drawn via website http://graphonline.ru/en/.

### 2. The Diameter and the Girth of $Γ ( ℤ n [ X ] ​ ] )$

In order to give the complete characterization of the diameter of $Γ(ℤn[X]​])$, we need the following lemma.

### Lemma 2.1. ([4, Chapter 1, Exercise 2(iii)] and [7, Theorem 5])

Let R be a commutative ring with identity. Then the following assertions hold.

• (1) If $f∈Z(R[X])$, then there exists a nonzero element r ∈ R such that rf=0.

• (2) If R is a Noetherian ring and $f∈Z(R[​[X]​])$, then there exists a nonzero element r ∈ R such that rf=0.

Let R be a commutative ring with identity. For a nonempty subset C of R, let $C[X]​]$ be the subset of $R[X]​]$ consisting of elements whose coefficients belong to C. For an element $f=∑ i≥0aiXi∈R[X]​]$, the order of f is defined to be the smallest nonnegative integer n such that $an≠0$ and is denoted by ord(f).

### Theorem 2.2.

The following statements hold.

• (1) $diam(Γ(ℤn[X]​]))=1$ if (and only if) n=p2 for some prime p.

• (2) $diam(Γ(ℤn[X]​]))=2$ if (and only if) n=pr for some prime p and some integer r ≥ 3, or n=pq for some distinct primes p and q.

• (3) $diam(Γ(ℤn[X]​]))=3$ if (and only if) n=pqr for some distinct primes p, q and some integer r ≥ 2.

Proof. Before proving the result, we note that for all integers $n≥2$, $ℤn$ is a Noetherian ring.

(1) Suppose that n=pr for some prime p and some integer r ≥ 3. Let f and g be two distinct elements of $Z(ℤp2[X]​])$. Then by Lemma 2.1, f and g are elements of $Z(ℤp2)[X]​]$. Note that $Z(ℤp2)={p,2p,…,(p−1)p}$; so the product of any two elements of $Z(ℤp2)$ is zero. Hence fg=0 in $ℤp2[X]​]$. This indicates that $Γ(ℤp2[X]​])$ is a complete graph. Thus $diam(Γ(ℤp2[X]​]))=1$.

(2) Suppose that n=pr, where p is a prime and r is an integer greater than or equal to 3. Let f and g be two distinct elements of $Z(ℤpr[X]​])$. Then by Lemma 2.1, f and g are elements of $Z(ℤpr)[X]​]$. Note that $Z(ℤpr)={p,2p,…,(pr−1−1)p}$; so for all $a∈Z(ℤpr)$, $apr−1=0$ in $ℤpr$. Hence $f−pr−1−g$ is a path in $Γ(ℤpr[X]​])$, which implies that $diam(Γ(ℤpr[X]​]))≤2$. Thus $diam(Γ(ℤpr[X]​]))=2$.

Suppose that n=pq, where p and q are distinct primes. Let $A={p,2p,…,(q−1)p}$ and $B={q,2q,…,(p−1)q}$. Then $A∩B=∅$ and $Z(ℤpq)=A∪B$. Let $f∈Z(ℤpq[X]​])$. Then by Lemma 2.1, there exists an element $r∈Z(ℤpq)$ such that rf=0. Note that for any $a1,a2∈A$ and $b1,b2∈B$, $a1a2≠0$ and $b1b2≠0$ in $ℤpq$; so if r ∈ A (resp., r ∈ B), then $f∈B[X]​]$ (resp., $f∈A[X]​]$). Therefore $Z(ℤpq[X]​])=A[X]​]∪B[X]​]$. Note that $A[X]​]∩B[X]​]=∅$ and for any a ∈ A and b ∈ B, ab=0. Hence $Γ(ℤpq[X]​])$ is a complete bipartite graph. Thus $diam(Γ(ℤpq[X]​]))=2$.

(3) Suppose that n=pqr, where p, q are distinct primes and r is an integer greater than or equal to 2. Then $pX,qX∈Z(ℤpqr[X]​])$ with $(pX)(qX)≠0$ in $ℤpqr[X]​]$; so $diam(Γ(ℤpqr[X]​]))≥2$. Suppose to the contrary that there exists an element $f∈Z(ℤpqr[X]​])$ such that $pX−f−qX$ is a path in $Γ(ℤpqr[X]​])$. Let a be the coefficient of $Xord(f)$ in f. Then ap=0=aq in $ℤpqr$; so a is a multiple of pqr. Therefore a=0 in $ℤpqr$. This is absurd. Hence $diam(Γ(ℤpqr[X]​]))≥3$. Thus $diam(Γ(ℤpqr[X]​]))=3$ [2,Theorem 2.3].

Figure 1. The diameter of some zero-divisor graphs

We next study the girth of $Γ(ℤn[X]​])$.

### Proposition 2.3.

If p is a prime and r ≥ 2 is an integer, then $g(Γ(ℤpr[X]​]))=3$.

Proof. It suffices to note that $pr−1−pr−1X−pr−1X2−pr−1$ is a cycle of length 3 in $Γ(ℤpr[X]​])$.

### Proposition 2.4.

If p and q are distinct primes, then $g(Γ(ℤpq[X]​]))=4$.

Proof. Note that by the proof of Theorem 2.2(2), $Γ(ℤpq[X]​])$ is a complete bipartite graph; so $Γ(ℤpq[X]​])$ does not have a cycle of length 3. Let A and B be as in the proof of Theorem 2.2(2). Then for any f ∈ A[X] and g ∈ B[X], pX-g-f-qX-pX is a cycle of length 4 in $Γ(ℤpq[X]​])$. Thus $g(Γ(ℤpq[X]​]))=4$.

### Lemma 2.5.

If $g(Γ(ℤn[X]​]))=3$, then $g(Γ(ℤmn[X]​]))=3$ for all integers $m≥1$.

Proof. Let m be any positive integer. Note that if f-g-h-f is a cycle of length 3 in $Γ(ℤn[X]​])$, then mf-mg-mh-mf is a cycle of length 3 in $Γ(ℤmn[X]​])$. Thus $g(Γ(ℤmn[X]​]))=3$.

### Lemma 2.6.

Let p and q be distinct primes. Then $g(Γ(ℤpqr[X]​]))=3$ for any prime r.

Proof. If r=p, then p-pq-pqX-p is a cycle of length 3 in $Γ(ℤp2q[X]​])$. If r=q, then q-pq-pqX-q is a cycle of length 3 in $Γ(ℤpq2[X]​])$. Suppose that r ≠ p and r ≠ q. Then pq-qr-pr-pq is a cycle of length 3 in $Γ(ℤpqr[X]​])$. Thus $g(Γ(ℤpqr[X]​]))=3$ for any prime r.

### Proposition 2.7.

Let p and q be distinct primes. Then $g(Γ(ℤpqr[X]​]))=3$ for any integer r ≥ 2.

Proof. Note that r is a multiple of some prime. Thus the result follows directly from Lemmas 2.5 and 2.6.

By Propositions 2.3, 2.4 and 2.7, we can completely characterize the girth of $Γ(ℤn[X]​])$ as follows:

### Theorem 2.8.

The following statements hold.

• (1) $g(Γ(ℤn[X]​]))=3$ if (and only if) each of the following conditions holds.

• (a) n=pr for some prime p and integer r ≥ 2.

• (b) n=pqr for some distinct primes p, q and integer r ≥ 2.

• (2) $g(Γ(ℤn[X]​]))=4$ if (and only if) n=pq for some distinct primes p and q.

Figure 2. The girth of some zero-divisor graphs

### 3. The Chromatic Number of $Γ ( ℤ n [ X ] ​ ] )$

In this section, we calculate the chromatic number of $Γ(ℤn[X]​])$. Clearly, if there exists a clique in a graph, then the chromatic number of the graph is greater than or equal to the size of the clique. Hence in order to find the chromatic number of $Γ(ℤn[X]​])$, we investigate to find a (maximal) clique of $Γ(ℤn[X]​])$.

### Lemma 3.1.

If r ≥ 2 is an integer, $n=p1⋯pr$ for distinct primes $p1,…,pr$, and $C={npi|i=1,…,r}$, then C is a maximal clique of $Γ(ℤn[X]​])$.

Proof. Note that the product of any two distinct members of C is zero in $ℤn[X]​]$; so C is a clique. Suppose to the contrary that there exists an element $f∈Z(ℤn[X]​])∖C$ such that cf=0 in $ℤn[X]​]$ for all c ∈ C. Let a be the coefficient of $Xord(f)$ in $f$. Then ca=0 in $ℤn$; so $a$ is a multiple of pi for all $i=1,…,r$. Hence a is a multiple of n, i.e., a=0 in $ℤn$. This is a contradiction. Thus C is a maximal clique of $Γ(ℤn[X]​])$.

### Proposition 3.2.

If $r≥2$ is an integer and $n=p1⋯pr$ for distinct primes $p1,…,pr$, then $χ(Γ(ℤn[X]​]))=r$.

Proof. Let $C={npi|i=1,…,r}$. Then by Lemma 3.1, C is a maximal clique of $Γ(ℤn[X]​])$. For each $i=1,…,r$, let $i¯$ be the color of $npi$. Clearly, $Z(ℤn[X]​])∖C$ is a nonempty set. For each $f∈Z(ℤn[X]​])∖C$, let $Sf={c∈C|f$ and c are not adjacent}. Then by Lemma 3.1, C is a maximal clique of $Γ(ℤn[X]​])$; so Sf is a nonempty set. Hence we can find the smallest integer $k∈{1,…,r}$ such that $npk∈Sf$. In this case, we color f with $k¯$.

To complete the proof, it remains to check that any two vertices of $Γ(ℤn[X]​])$ with the same color cannot be adjacent. Fix an element $k∈{1,…,r}$ and let f and g be distinct vertices of $Γ(ℤn[X]​])$ with the same color $k-$. Since C is a clique, f and g cannot belong to C at the same time. Suppose that f ∈ C and $g∈Z(ℤn[X]​])∖C$. Then $f=npk$; so by the coloring of g, f and g are not adjacent. Suppose that $f,g∈Z(ℤn[X]​])∖C$ and write $f=∑ i≥0aiXi$ and $g=∑ i≥0biXi$. Then by the coloring of f and g, f and g are not adjacent to $npk$; so $npkf≠0$ and $npkg≠0$ in $ℤn[X]​]$. Let α be the smallest nonnegative integer such that $npkaα≠0$ in $ℤn$ and let β be the smallest nonnegative integer such that $npkbβ≠0$ in $ℤn$. Then $a0,…,aα−1,b0,…,bβ−1$ are divided by pk and $aα,bβ$ are not divided by pk; so the coefficient of $Xα+β$ in fg is not divided by pk. Therefore $fg≠0$ in $ℤn[X]​]$. Hence f and g are not adjacent.

Thus we conclude that $χ(Γ(ℤn[X]​]))=r$.

We denote the set of nonnegative integers by $ℕ0$.

### Lemma 3.3.

If n is a multiple of the square of a prime, then $Γ(ℤn[X]​])$ has an infinite clique.

Proof. Suppose that n is a multiple of the square of a prime.

Case 1. $n=p12a1⋯pr2ar$ for distinct primes $p1,…,pr$ and positive integers $a1,…,ar$. In this case, let $C={nXm|m∈ℕ0}$. Then the product of any two elements of C is zero in $ℤn[X]​]$; so C is an infinite clique of $Γ(ℤn[X]​])$.

Case 2. $n=p12a1⋯pr2arq12b1+1⋯qs2bs+1$ for distinct primes $p1,…,pr,$ $q1,…,qs$ and nonnegative integers $a1,…,ar,b1,…,bs$, not all zero. In this case, let $k=p1a1⋯prarq1b1+1⋯qsbs+1$ and let $C={kXm|m∈ℕ0}$. Then the product of any two elements of C is zero in $ℤn[X]​]$; so C is an infinite clique of $Γ(ℤn[X]​])$.

By Cases 1 and 2, $Γ(ℤn[X]​])$ has an infinite clique.

### Proposition 3.4.

Let n be a multiple of the square of a prime. Then $χ(Γ(ℤn[X]​]))=∞$.

Proof. By Lemma 3.3, $Γ(ℤn[X]​])$ has an infinite clique; so $cl(Γ(ℤn[X]​]))=∞$.

Thus $χ(Γ(ℤn[X]​]))=∞$.

By Propositions 3.2 and 3.4, we obtain the main result in this section.

### Theorem 3.5.

The following statements hold.

• (1) $χ(Γ(ℤn[X]​]))=r$ if (and only if) $n=p1⋯pr$ for some distinct primes $p1,…,pr$.

• (2) $χ(Γ(ℤn[X]​]))=∞$ if (and only if) n is a multiple of the square of some prime.

Figure 3. The coloring of some zero-divisor graphs

We would like to thank the referee for several valuable suggestions.

1. D. F. Anderson, M. C. Axtell, and J. A. Stickles, Jr, Zero-divisor graphs in commutative rings, Commutative Algebra: Noetherian and Non-Noetherian Perspectives, 23-45, Springer, New York, 2011.
2. D. F. Anderson and P. S. Livingston, The zero-divisor graph of a commutative ring, J. Algebra, 217(1999), 434-447.
3. D. D. Anderson and M. Naseer, Beck’s coloring of a commutative ring, J. Algebra, 159(1993), 500-514.
4. M. F. Atiyah and I. G. MacDonald, Introduction to commutative algebra, Addison-Wesley Series in Math., Westview Press, 1969.
5. M. Axtell, J. Coykendall, and J. Stickles, Zero-divisor graphs of polynomials and power series over commutative rings, Comm. Algebra, 33(2005), 2043-2050.
6. I. Beck, Coloring of commutative rings, J. Algebra, 116(1988), 208-226.
7. D. E. Fields, Zero divisors and nilpotent elements in power series rings, Proc. Amer. Math. Soc., 27(1971), 427-433.
8. S. Mulay, Cycles and symmetries of zero-divisors, Comm. Algebra, 30(2002), 3533-3558.
9. S. J. Pi, S. H. Kim, and J. W. Lim, The zero-divisor graph of the ring of integers modulo n, Kyungpook Math. J., 59(2019), 591-601.