n [ X ]] ">
검색
Article Search

JMB Journal of Microbiolog and Biotechnology

OPEN ACCESS eISSN 0454-8124
pISSN 1225-6951
QR Code

Article

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

Published online December 31, 2020

Copyright © Kyungpook Mathematical Journal.

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 n1 such that KnG. If KnG for all integers n1, 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/.

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 fZ(R[X]), then there exists a nonzero element r ∈ R such that rf=0.

  • (2) If R is a Noetherian ring and fZ(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= i0aiXiR[X]], the order of f is defined to be the smallest nonnegative integer n such that an0 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 n2, 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,,(p1)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,,(pr11)p}; so for all aZ(pr), apr1=0 in pr. Hence fpr1g 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,,(q1)p} and B={q,2q,,(p1)q}. Then AB= and Z(pq)=AB. Let fZ(pq[X]]). Then by Lemma 2.1, there exists an element rZ(pq) such that rf=0. Note that for any a1,a2A and b1,b2B, a1a20 and b1b20 in pq; so if r ∈ A (resp., r ∈ B), then fB[X]] (resp., fA[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,qXZ(pqr[X]]) with (pX)(qX)0 in pqr[X]]; so diam(Γ(pqr[X]]))2. Suppose to the contrary that there exists an element fZ(pqr[X]]) such that pXfqX 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 pr1pr1Xpr1X2pr1 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 m1.

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

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=p1pr 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 fZ(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 r2 is an integer and n=p1pr 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 fZ(n[X]])C, let Sf={cC|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 npkSf. 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 gZ(n[X]])C. Then f=npk; so by the coloring of g, f and g are not adjacent. Suppose that f,gZ(n[X]])C and write f= i0aiXi and g= i0biXi. Then by the coloring of f and g, f and g are not adjacent to npk; so npkf0 and npkg0 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 fg0 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=p12a1pr2ar for distinct primes p1,,pr and positive integers a1,,ar. In this case, let C={nXm|m0}. 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=p12a1pr2arq12b1+1qs2bs+1 for distinct primes p1,,pr, q1,,qs and nonnegative integers a1,,ar,b1,,bs, not all zero. In this case, let k=p1a1prarq1b1+1qsbs+1 and let C={kXm|m0}. 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=p1pr 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
  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.
    KoreaMed CrossRef
  2. D. F. Anderson and P. S. Livingston, The zero-divisor graph of a commutative ring, J. Algebra, 217(1999), 434-447.
    CrossRef
  3. D. D. Anderson and M. Naseer, Beck’s coloring of a commutative ring, J. Algebra, 159(1993), 500-514.
    CrossRef
  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.
    CrossRef
  6. I. Beck, Coloring of commutative rings, J. Algebra, 116(1988), 208-226.
    CrossRef
  7. D. E. Fields, Zero divisors and nilpotent elements in power series rings, Proc. Amer. Math. Soc., 27(1971), 427-433.
    CrossRef
  8. S. Mulay, Cycles and symmetries of zero-divisors, Comm. Algebra, 30(2002), 3533-3558.
    CrossRef
  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.