# On the Genus of the Zero-Divisor Graph ofZn

Authors: Huadong Su; Pailing Li
Journal: International Journal of Combinatorics
 (2014)

---

## Abstract

LetR be a commutative ring with identity. The zero-divisor graph of R, denoted Γ(R), is the simple graph whose vertices are the nonzero zero-divisors of R, and two distinct vertices x and y are linked by an edge if and only if xy=0. The genus of a simple graph G is the smallest integer g such that G can be embedded into an orientable surface Sg. In this paper, we determine that the genus of the zero-divisor graph of Zn, the ring of integers modulo n, is two or three.


---

## Body

## 1. Introduction

This paper concerns the zero-divisor graphs of rings. For a commutative ringR, define a simple graph calledzero-divisor graph, denoted by Γ(R), whose vertices are the nonzero zero-divisors of R, and two distinct vertices x and y are adjacent if and only if xy=0 in R. This definition was first introduced by Beck in [1]. However, he let all elements of R be the vertices of the graph and mainly considered the coloring of this graph. Here our definition is the same as in [2], where some basic properties of Γ(R) are established. The zero-divisor graph, as well as other graphs of rings, is an active research topic in the last two decades (see, e.g., [3–11]).Let us first recall some needed notions in graph theory. LetG be a simple graph, that is, no loops and no multiedges. Thedegree of a vertex v∈G, denoted by deg⁡(v), is the number of edges of G incident with v. If V′⊆V(G), then G-V′ is the subgraph of G obtained by deleting the vertices in V′ and all edges incident with them. If V′={x∈V∣deg⁡(x)=0 or 1}, then we use G~ for the subgraph G-V′ and call it thereduction of G. Acomplete bipartite graph is a bipartite graph (i.e., a set of graph vertices decomposed into two disjoint sets such that no two vertices within the same set are adjacent) such that every pair of vertices in the two sets are adjacent. The complete bipartite graph with partitions of sizes m and n is denoted by Km,n. Thecomplete graphon n vertices, denoted Kn, is the graph in which every pair of distinct vertices is joined by an edge. A surface is said to be ofgenusg if it is topologically homomorphic to a sphere with g handles. A graph G that can be drawn without crossings on a compact surface of genus g, but not on one of genus g-1, is called a graph ofgenusg. We write γ(G) for the genus of the graph G. It is clear that γ(G)=γ(G~), where G~ is the reduction of G, and γ(H)≤γ(G) for any subgraph H of G.Determining the genus of a graph is one of the most fundamental problems in topological graph theory. It has been shown to be NP-complete by Thomassen in [12]. Several papers focus on the genera of zero-divisor graphs. For instance, in [6, 7, 13, 14], the authors studied the planar zero-divisor graphs (genus equals to 0); Wang et al. investigated the genus one zero-divisor graphs in [11, 15, 16], respectively; and Bloomfield and Wickham determined all local rings whose zero-divisor graphs have genus two in [8]. In this paper, we study the zero-divisor graph of Zn, the ring of integers modulo n. In particular, we determine when γ(Γ(Zn))=2 or 3. Here we first summarize the results about the genus of Γ(Zn) from [5, Theorem 5.1(a)], [8, Theorem 1], and [16, Section 5].Theorem 1.
LetΓ(Zn) be not empty. Then the following hold. (1)
γ(Γ(Zn))=0 if and only if n∈{8,12,16,18,25,27,2p,3p}, where p is prime.(2)
γ(Γ(Zn))=1 if and only if n∈{20,24,28,32,49}.(3)
γ(Γ(Zpt))=2 if and only if pt=81.
All rings considered in this paper will be commutative rings with identity. Leta be an element of a ring R. Then the principal ideal generated by a is denoted by 〈a〉. For a set A, |A| means the order of A.


## 2. The Genus ofΓ(Zn)

The following two lemmas are frequently used in the proofs of our main results.Lemma 2 ([17, Theorem 6.38]).
γ
(
K
n
)
=
{
(
1
/
12
)
(
n
-
3
)
(
n
-
4
)
}, where {x} is the least integer that is greater than or equal to x.Lemma 3 ([17, Theorem 6.37]).
γ
(
K
m
,
n
)
=
{
(
1
/
4
)
(
m
-
2
)
(
n
-
2
)
}, where {x} is the least integer that is greater than or equal to x.Lemma 4 ([17, Corollary 6.15]).
Suppose a simple graphG is connected with v≥3 vertices and e edges. If G has no triangles, then γ(G)≥(e/4)-(v/2)+1.Lemma 5.
LetG be a graph with vertex set {u1,u2,u3,u4;v1,…,v7;w1,w2,w3,w4} and the edge set {(ui,vj)∣1≤i≤4,1≤j≤7}∪{(vi,wj)∣1≤i≤3,1≤j≤3}. Then γ(G)≥4.Proof.
Note that there are no triangles inG. As G has 40 edges and 15 vertices, γ(G)≥4 by Lemma 4.We first consider the case thatn has only one prime divisor.Theorem 6.
Letn=pt, where p is prime and t≥2. Then γ(Γ(Zn))=3 if and only if n=64.Proof.
(⇒). Let I=〈pt-1〉-{0}. Then |I|=p-1. As any two vertices in I are adjacent, there exists a complete subgraph Kp-1 in Γ(Zn). It follows that if p≥11, then γ(Γ(Zn))≥γ(Γ(K10))=4 by Lemma 2. Therefore, p≤7. We proceed with three cases.
Case
1 (p=5 or 7). By Theorem 1, γ(Γ(Z52))=0 and γ(Γ(Z72))=1. So we can further assume t≥3. Let I=〈pt-2〉-〈pt-1〉 and J=〈pt-1〉-{0}. Then I∩J is empty and |I|=p2-p≥20, |J|=p-1≥4. As each vertex of I is adjacent to every vertex of J, there exists a complete bipartite subgraph K4,20 in Γ(Zn), which implies that γ(Γ(Zn))≥γ(Γ(K4,20))=9 by Lemma 3.
Case
2 (p=3). From Theorem 1, we have γ(Γ(Z32))=0, γ(Γ(Z33))=0, and γ(Γ(Z81))=2. So we may assume t≥5. Let I=〈3t-3〉-〈3t-2〉 and J=〈3t-2〉-{0}. Then I∩J is empty and |I|=33-32=18, |J|=32-1=8. Since each vertex of I is adjacent to every vertex of J, Γ(Zn) contains a complete bipartite subgraph K8,18, which implies that γ(Γ(Zn))≥γ(Γ(K8,18))=24 by Lemma 3.
Case
3 (p=2). By Theorem 1, γ(Γ(Z2t))=0 if t=2,3,4, and γ(Γ(Z25))=1.
Ifn≠64, we can assume t≥7. We let I=〈2t-4〉-〈2t-3〉, J=〈2t-3〉-{0}. Then |I|=24-23=8, |J|=23-1=7. Note that each vertex of I is adjacent to each vertex of J and I∩J is empty, so there exists a complete bipartite subgraph K7,8 in Γ(Zn), which implies that γ(Γ(Zn))≥γ(K7,8)=8 by Lemma 3. Therefore, n=64.
(⇐). For n=64, let I=〈4〉-〈16〉 and J=〈16〉-{0}. Then |I|=12, |J|=3, and I∩J is empty. Since each vertex in I is adjacent to each vertex in J, there exists a complete bipartite subgraph K3,12 in Γ(Z64), which implies that γ(Γ(Z64))≥γ(K3,12)=3 by Lemma 3. On the other hand, we can embed the reduction of Γ(Z64) into S3 as shown in Figure 1. Therefore, γ(Γ(Z64))=3.
This completes our proof.Figure 1
The reduction ofΓ(Z64).We now consider the case thatn has exactly two prime divisors.Theorem 7.
Letn=psqt, where p<q are primes and s,t≥1. Then γ(Γ(Zn))=2 if and only if n∈{35,36,44,50}, and γ(Γ(Zn))=3 if and only if n∈{45,52,54}.Proof.
We first prove that if2≤γ(Γ(Zn))≤3 then n∈{35,36,44,50,45,52,54}. We then determine γ(Γ(Zn)) for each n∈{35,36,44,50,45,52,54}. We proceed with four cases to get the result.
Case
1 (s=t=1). It is clear that Γ(Zn) is a complete bipartite graph Kp-1,q-1. In this case, if p=5 and q≥11, then K4,10 is a subgraph of Γ(Zn); it follows that γ(Γ(Zn))≥γ(K4,10)=4 by Lemma 3. If p=2 or p=3, by Theorem 1, we have γ(Γ(Zn))=0. So p=5, q=7; that is, n=35.
Case
2 (s=1 and t≥2). If t≥3, set I=〈pqt-2〉-〈pqt-1〉 and J=〈q2〉-{0}. Then I∩J is empty and each vertex in I is adjacent to each vertex in J. If q≥5, then |I|=q2-q≥20, |J|=pqt-2-1≥9, which implies that Γ(Zn) contains a complete bipartite subgraph K9,20. Therefore γ(Γ(Zn))≥γ(K9,20)=32 by Lemma 3. If q=3 and t≥4, then |I|=q2-q=6, |J|=pqt-2-1≥17, which implies that there exists a complete bipartite subgraph K6,17 in Γ(Zn). Therefore γ(Γ(Zn))≥γ(K6,17)=15 by Lemma 3. Hence, in this situation, we have n=2·33=54.
Consider nowt=2; that is, n=pq2. Let I=〈q〉-〈pq〉 and J=〈pq〉-{0}. Then I∩J is empty and |I|=pq-q, |J|=q-1. Notice that each vertex in I is adjacent to each vertex in J, so there exists a complete bipartite subgraph Kpq-q,q-1 in Γ(Zn). If q=7, then γ(Γ(Zn))≥γ(K7p-7,6)≥5. If q=5 and p=3 then γ(Γ(Zn))≥γ(K4,10)=4. By Theorem 1, we know γ(Γ(Z18))=0. So n=50.
Case
3 (s≥2 and t=1). Let I=〈ps〉-{0} and J=〈q〉-{0}. Then |I|=q-1, |J|=ps-1, and I∩J is empty. Since each vertex in I is adjacent to each vertex in J, there exists a complete bipartite subgraph Kq-1,ps-1 in Γ(Zn). Therefore γ(Γ(Zn))≥γ(Kq-1,ps-1). Simply checking, we can see that there are only seven cases satisfying the inequality γ(Kq-1,ps-1)≤3; thatis,n∈{2s×3,20,40,45,28,44,52}. By Theorem 1, we have γ(Γ(Z20))=1 and γ(Γ(Z28))=1. So n∈{2s×3,40,45,44,52}.
Forn=40, we set I={8,16,24,32}, J={5,10,15,20,25,30,35}, and K={4,12,28,36}. Note that each vertex in I is adjacent to each vertex in J, and the vertices 10, 20, and 30 are adjacent to each vertex in K, so by Lemma 5, γ(Γ(Z40))≥4.
For the casen=2s·3, by Theorem 1, we have γ(Γ(Z12))=0 and γ(Γ(Z24))=1. If s=4, that is, n=48, we set I={8,16,24,32}, J={6,12,18,24,30,36,42}, and K={4,20,28,44}. Note that each vertex in I is adjacent to each vertex in J, and the vertices 12, 24, and 36 are adjacent to each vertex in K, so by Lemma 5, γ(Γ(Z48))≥4. If s≥5, we set I=〈2s-1〉-〈6〉 and J=〈6〉-{0}. Then |I|=4, |J|=2s-1-1 and I∩J is empty. Since each vertex in I is adjacent to each vertex in J, there is a complete bipartite subgraph K4,2s-1-1 in Γ(Zn). It then follows that γ(Γ(Zn))≥γ(K4,2s-1-1)≥7 by Lemma 3.
Case
4 (s≥2 and t≥2). We set I=〈ps-1qt-1〉-{0}. Then |I|=pq-1. Since any two vertices in I are adjacent, there exists a complete subgraph Kpq-1 in Γ(Zn). If pq≥11, then γ(Γ(Zn))≥γ(K10)=4 by Lemma 2. So n=2s·3t or n=2s·5t. If n=2s·3t, set I=〈2s〉-{0} and J=〈3t〉-{0}; then |I|=3t-1, |J|=2s-1, and I∩J is empty. Since each vertex in I is adjacent to each vertex in J, there exists a complete bipartite subgraph K2s-1,3t-1 in Γ(Zn). If e1≥3 or e2≥3, then γ(Γ(Zn))≥4. So s=2, t=2; that is n=36. If n=2s·5t, similarly, there exists a complete bipartite subgraph K2s-1,5t-1 in Γ(Zn). Therefore, γ(Γ(Zn))≥γ(K2s-1,5t-1)≥6 by Lemma 3.
Now we have proved that if2≤γ(Γ(Zn))≤3, then n∈{35,36,44,50,45,52,54}.
In the following, we determineγ(Γ(Zn)) for each n∈{35,36,44,50,45,52,54}.
It is easy to see thatΓ(Z35)=K4,6. So γ(Γ(Z35))=2 by Lemma 3.
Forn=36, as mentioned in Case 4 above, Γ(Z36) contains a subgraph K3,8. So γ(Γ(Z36))≥γ(K3,8)=2. Γ(Z36) can be embedded into S2 as shown in Figure 2. So γ(Γ(Z36))=2.
Since the reductions of the graphsΓ(Z44) and Γ(Z52) are K3,10 and K3,12, respectively, we have γ(Γ(Z44))=γ(K3,10)=2 and γ(Γ(Z52))=γ(K3,12)=3, respectively.
Forn=50, as mentioned in Case 2 above, we have γ(Γ(Zn))≥γ(K4,5)=2 by Lemma 3. We can embed the reduction of the graph Γ(Z50) into S2 as shown in Figure 3. Thus, γ(Γ(Z50))=2.
Forn=45, we set I=〈9〉-{0} and J=〈5〉-{0}. Then |I|=4, |J|=8, and I∩J is empty. Since each vertex in I is adjacent to each vertex in J, there is a complete bipartite subgraph K4,8 in Γ(Z45). It then follows that γ(Γ(Z45))≥γ(K4,8)=3. On the other hand, we can embed the reduction of the graph Γ(Z45) into S3 as shown in Figure 4. Thus, γ(Γ(Z45))=3.
Forn=54, let I=〈6〉-〈18〉 and J=〈9〉-{0}. Then |I|=6, |J|=5, and I∩J is empty. Since each vertex in I is adjacent to each vertex in J, there exists a complete bipartite subgraph K5,6 in Γ(Z54). Therefore γ(Γ(Z54))≥γ(K5,6)=3. On the other hand, we can embed the graph Γ(Z54) into S3 as shown in Figure 5.
This completes the proof.Figure 2
The reduction ofΓ(Z36).Figure 3
The reduction ofΓ(Z50).Figure 4
The reduction ofΓ(Z45).Figure 5
The reduction ofΓ(Z54).The final case is thatn has more than two prime divisors.Theorem 8.
Letn=p1e1p2e2⋯pses (s≥3), where p1<p2<⋯<ps are primes. Then γ(Γ(Zn))=2 if and only if n=30, and γ(Γ(Zn))=3 if and only if n=42.Proof.
LetI=〈p1e1p2e2〉-{0} and J=〈n/p1e1p2e2〉-{0}. Then |I|=p3e3⋯pses-1, |J|=p1e1p2e2-1≥5 and I∩J is empty; moreover, every vertex in I is adjacent to each vertex in J. Thus, there exists a complete bipartite subgraph K|I|,|J| in Γ(Zn). It then follows that p3e3⋯pses≤7 as γ(Γ(Zn))≤3. So either n=2e13e2·5 or n=2e13e2·7.
For the former case, setI=〈2e13e2〉-{0} and J=〈5〉-{0}; then |I|=4, |J|=2e13e2-1 and I∩J is empty. Note that each vertex in I is adjacent to each vertex in J, so there exists a complete bipartite subgraph K4,2e13e2-1 in Γ(Zn). If 2e13e2-1≥9, then γ(Γ(Zn))≥4 by Lemma 3. So e1=e2=1; that is, n=30.
LetI=〈5〉-{0} and J=〈6〉-{0}. Then |I|=5, |J|=4, and I∩J is empty. Since each vertex in I is adjacent to each vertex in J, there exists a complete bipartite subgraph K4,5 in Γ(Z30). It then follows that γ(Γ(Z30))≥γ(K4,5)=2. On the other hand, we can embed Γ(Z30) into S2 as shown in Figure 6, so γ(Γ(Z30))=2.
For the latter case, with a similar argument above, we haven=42. Let I=〈7〉-{0} and J=〈6〉-{0}. Then |I|=5, |J|=6, and I∩J is empty. Since each vertex in I is adjacent to each vertex in J, there exists a complete bipartite subgraph K5,6 in Γ(Z42), which implies that γ(Γ(Z42))≥γ(K5,6)=3. On the other hand, we can embed Γ(Z42) into S3 as shown in Figure 7, so γ(Γ(Z42))=3.
This completes our proof.Figure 6
The reduction ofΓ(Z30).Figure 7
The reduction ofΓ(Z42).Now we have completely determined whenγ(Γ(Zn))=2 or 3. We summarize the result by the following theorem.Theorem 9.
(1)γ(Γ(Zn))=2 if and only if n∈{30,35,36,44,50,81}.
(2)γ(Γ(Zn))=3 if and only if n∈{42,45,52,54,64}.



---

*Source: 390732-2014-07-22.xml*