Article
KYUNGPOOK Math. J. 2019; 59(4): 591601
Published online December 23, 2019
Copyright © Kyungpook Mathematical Journal.
The Zerodivisor Graph of the Ring of Integers Modulo n
Seung Jun Pi, Se Hun Kim, Jung Wook Lim∗
Department of Mathematics, College of Natural Sciences, Kyungpook National University, Daegu, 41566, Republic of Korea
email : seungjunpi0@gmail.com
Department of Mathematics, Seoul National University, Seoul, 03080, Republic of Korea
email : shunhun33@gmail.com
Department of Mathematics, College of Natural Sciences, Kyungpook National University, Daegu, 41566, Republic of Korea
email : jwlim@knu.ac.kr
Received: October 15, 2018; Revised: September 5, 2019; Accepted: November 11, 2019
Abstract
Let ℤ
Keywords: zerodivisor graph, ring of integers modulo n, diameter, girth, clique, chromatic number.
1. Introduction
1.1. Preliminaries
In this subsection, we review some concepts from basic graph theory. Let
1.2. The Zerodivisor Graph of a Commutative Ring
Let
In [4], Beck first introduced the concept of the zerodivisor graphs of commutative rings and in [3], Anderson and Nazeer continued the study. In their papers, all elements of
For more on the zerodivisor graph of a commutative ring, the readers can refer to a survey article [1].
Let ℤ
2. The Diameter and the Girth of Γ(ℤ_{n} )
Our first result in this section is the complete characterization of the diameter of Γ(ℤ
Theorem 2.1
(1) diam(Γ(ℤ
(2)diam(Γ(ℤ
(3)diam(Γ(ℤ
(4)diam(Γ(ℤ
(1) If
(2) If
(3) If
If
(4) Suppose that
We next study the girth of Γ(ℤ
Lemma 2.2
Proof. Note that if
The next example shows that Lemma 2.2 cannot be extended to the case of girth 4.
Example 2.3
(1) Note that g(Γ(ℤ_{12})) = 4. In fact, 3 ~ 4 ~ 6 ~ 8 ~ 3 is a cycle of length 4 in Γ(ℤ_{12}). However, g(Γ(ℤ_{24})) = 3 because 6 ~ 8 ~ 12 ~ 6 is a cycle of length 3 in Γ(ℤ_{24}).
(2) In general, g(Γ(ℤ_{4}
Proposition 2.4
If
If
Proposition 2.5
(1) g(Γ(ℤ_{pr})) = ∞ if and only if
(2) g(Γ(ℤ_{pr})) = 3 if and only if each of the following conditions holds.
(a)
p = 2 andr ≥ 4.(b)
p = 3 andr ≥ 3.(c)
p ≥ 5 andr ≥ 2.
(1) It is obvious that Γ(ℤ_{4}), Γ(ℤ_{8}) and Γ(ℤ_{9}) have no cycles. Thus the equivalence follows.
(2) If
If
If
Proposition 2.6
(1) g(Γ(ℤ
(2) g(Γ(ℤ
(a)
n = 2^{r} q ^{s} for some prime q ≥ 3and some integers r ≥ 1and s ≥ 2.(b)
n = 2^{r} q for some prime q ≥ 3and some integer r ≥ 3.(c)
n = 3^{r} q ^{s} for some prime q ≥ 5and some integers r ≥ 1and s ≥ 2.(d)
n = 3^{r} q for some prime q ≥ 5and some integer r ≥ 2.(e)
n =p ^{r} q ^{s} for some primes q > p ≥ 5and some integers r ,s ≥ 1except for r =s = 1.
(3) g(Γ(ℤ
(1) If
(2) Let
(3) If
Let
In the next remark, we construct a cycle of length 3 in Γ(ℤ
Remark 2.7
(1) Let
(2) Let
(3) Let
(4) Let
(5) Let
By Propositions 2.4, 2.5, and 2.6, we obtain
Theorem 2.8
The following statements hold.
(1) g(Γ(ℤ
(a)
n = 4, 8, 9.(b)
n = 2q for some primeq ≥ 3.
(2) g(Γ(ℤ
(a)
n =pq for some distinct primesp ,q ≥ 3.(b)
n = 4q for some primeq ≥ 3.
(3) g(Γ(ℤ
3. The Chromatic Number of Γ(ℤ_{n} )
In this section, we calculate the chromatic number of Γ(ℤ

Step 1. Find a maximal clique
C in Γ(ℤ_{n} ) and color vertices inC . 
Step 2. Color vertices in Z(ℤ
_{n} )C by colors used in Step 1. 
Step 3. Confirm that there are no adjacent vertices having the same color.
Lemma 3.1
Note that the product of any two distinct members of
Theorem 3.2
Let
To complete the proof, we need to check that any two elements in Z(ℤ
Example 3.3
Consider Γ(ℤ_{15}). Let
For the detail, see Figure 3. Note that in Figure 3, 1̄ and 2̄ are represented by blue and red, respectively.
Lemma 3.4
Note that the product of any two distinct elements of
Theorem 3.5
Let
Now, it remains to check that any two vertices with the same color cannot be adjacent. Let
In either case, Γ(ℤ
Example 3.6
Consider Γ(ℤ_{36}). Let
For the detail, see Figure 4. Note that in Figure 4, 1̂, 2̂, 3̂, 4̂ and 5̂ are represented by green, red, blue, pink and brown, respectively.
Lemma 3.7
Proof
We first note that
Theorem 3.8
Proof
Let
There exists an element
It remains to show that there are no adjacent vertices with the same color. Let
Example 3.9
Consider Γ(ℤ_{18}). Let
For the detail, see Figure 5. Note that in Figure 5, 1̂, 2̂ and 1̄ are represented by red, green and blue, respectively.
Example 3.10
Consider Γ(ℤ_{72}). Let
For the detail, see Figure 6. Note that in Figure 6, 1̄, 1̂, 2̂, 3̂, 4̂ and 5̂ are represented by yellow, red, pink, blue, skyblue and green, respectively.
Acknowledgements
The authors would like to thank the referee for his/her several valuable suggestions. The third author was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (2017R1C1B1008085).
Figures
References
 DF. Anderson, MC. Axtell, and JA. Stickles.
Zerodivisor graphs in commutative rings . Commutative Algebra: Noetherian and NonNoetherian Perspectives,, Springer, New York, 2011:2345.  DF. Anderson, and PS. Livingston.
The zerodivisor graph of a commutative ring . J Algebra.,217 (1999), 434447.  DD. Anderson, and M. Naseer.
Beck’s coloring of a commutative ring . J Algebra.,159 (1993), 500514.  I. Beck.
Coloring of commutative rings . J Algebra.,116 (1988), 208226.  S. Mulay.
Cycles and symmetries of zerodivisors . Comm Algebra.,30 (2002), 35333558.