Article
KYUNGPOOK Math. J. 2019; 59(4): 591-601
Published online December 23, 2019
Copyright © Kyungpook Mathematical Journal.
The Zero-divisor 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
e-mail : seungjunpi0@gmail.com
Department of Mathematics, Seoul National University, Seoul, 03080, Republic of Korea
e-mail : shunhun33@gmail.com
Department of Mathematics, College of Natural Sciences, Kyungpook National University, Daegu, 41566, Republic of Korea
e-mail : jwlim@knu.ac.kr
Received: October 15, 2018; Revised: September 5, 2019; Accepted: November 11, 2019
Abstract
Let ℤ
Keywords: zero-divisor 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 Zero-divisor Graph of a Commutative Ring
Let
In [4], Beck first introduced the concept of the zero-divisor graphs of commutative rings and in [3], Anderson and Nazeer continued the study. In their papers, all elements of
For more on the zero-divisor 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(Γ(ℤ
(2) g(Γ(ℤ
(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 = 2r q s for some prime q ≥ 3and some integers r ≥ 1and s ≥ 2.(b)
n = 2r q for some prime q ≥ 3and some integer r ≥ 3.(c)
n = 3r q s for some prime q ≥ 5and some integers r ≥ 1and s ≥ 2.(d)
n = 3r 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, sky-blue 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).
References
- DF. Anderson, MC. Axtell, and JA. Stickles.
Zero-divisor graphs in commutative rings . Commutative Algebra: Noetherian and Non-Noetherian Perspectives,, Springer, New York, 2011:23-45. - DF. Anderson, and PS. Livingston.
The zero-divisor graph of a commutative ring . J Algebra.,217 (1999), 434-447. - DD. Anderson, and M. Naseer.
Beck’s coloring of a commutative ring . J Algebra.,159 (1993), 500-514. - I. Beck.
Coloring of commutative rings . J Algebra.,116 (1988), 208-226. - S. Mulay.
Cycles and symmetries of zero-divisors . Comm Algebra.,30 (2002), 3533-3558.