NONPLANARITY OF UNIT GRAPHS AND CLASSIFICATION OF THE TOROIDAL ONES

A. K. DAS, H. R. MAIMANI, M. R. POURNAKI, AND S. YASSEMI

Abstract. The unit graph of a ring R with nonzero identity is the graph in which the vertex set is R, and two distinct vertices x and y are adjacent if and only if x + y is a unit in R. In this paper, we derive several necessary conditions for the nonplanarity of the unit graphs of finite commutative rings with nonzero identity, and determine, up to isomorphism, all finite commutative rings with nonzero identity whose unit graphs are toroidal.

1. Introduction

Algebraic combinatorics is an area of mathematics which employs methods of abstract algebra in various combinatorial contexts and vice versa. Associating a graph to an algebraic structure is a research subject in this area and has attracted considerable attention. The research in this subject aims at exposing the relationship between algebra and graph theory and at advancing the application of one to the other. In fact, there are three major problems in this area: (1) characterization of the resulting graphs, (2) characterization of the algebraic structures with isomorphic graphs, and (3) realization of the connections between the algebraic structures and the corresponding graphs. In 1988, Beck [7] introduced the idea of a zero-divisor graph of a commutative ring R with nonzero identity. He defined Γ_{0}(R) to be the graph in which the vertex set is R, and two distinct vertices x and y are adjacent if and only if xy = 0. He was mostly concerned with coloring of Γ_{0}(R). Beck conjectured that χ(R) = ω(R), where χ(R) and ω(R) denote, respectively, the chromatic number and the clique number of Γ_{0}(R). Such graphs are called weakly perfect graphs. This investigation of coloring of a commutative ring was then continued by Anderson and Naseer in [1]. They gave a counterexample for the above conjecture of Beck. In [3], Anderson and Livingston proposed a different method of associating a zero-divisor graph to a commutative ring R, and according to them this gives a better illustration of the zero-divisor structure of the ring. They defined Γ(R) to be the graph in which the vertex set consists of all the nonzero zero-divisors of R, and two distinct vertices x and y are adjacent if and only if xy = 0. For a survey and recent results concerning zero-divisor graphs, we refer the reader to [2]. In literature, one can find a number of different types of graphs attached to rings or other algebraic structures. For a survey of recent results concerning graphs attached to rings, we refer the reader to [12].

2000 Mathematics Subject Classification. Primary: 05C75; Secondary: 13M05.

Key words and phrases. Finite commutative ring, Unit graph, Genus.

This research was in part supported by a grant from IPM (H. R. Maimani: No. 91050214, M. R.

Pournaki: No. 92130115, and S. Yassemi: No. 92130214), by a grant from INSF (M. R. Pournaki), and by a grant from the Center for International Scientific Studies and Collaboration (CISSC), Iran, and Égide – Programme Gundishapur 2012, Hubert Curien Partnership, France (M. R. Pournaki and S. Yassemi: No. 27462PL).

The present paper deals with what is known as the unit graph of a ring, a notion that generalizes the idea of Grimaldi [11] who introduced and studied in detail a graph G(ℤ_{n}) in which the vertex set is the ring ℤ_{n} of integers modulo a positive integer n, and two distinct vertices x and y are adjacent if and only if x + y is a unit in ℤ_{n}. In general, given an arbitrary ring R with nonzero identity, its unit graph G(R) is defined to be the graph in which the vertex set is R, and two distinct vertices x and y are adjacent if and only if x + y is a unit in R. Some of the properties of this graph have been studied in detail in [5, 13, 14, 15, 16]. The graphs in Figure 1 are the unit graphs of the rings indicated.

[figure: 0; 1; 2; G(ℤ_{3}); 0; 1; 2; 3; G(ℤ_{4}); 10; 11; 00; 01; G(ℤ_{2} × ℤ_{2})]

Figure 1. The unit graphs of some specific rings.

It is easy to see that, given any two rings R and S, if R ≅ S as rings, then G(R) ≅ G(S) as graphs. This point is illustrated in Figure 2 for the unit graphs of two isomorphic rings ℤ_{3} × ℤ_{2} and ℤ_{6}.

[figure: 00; 11; 21; 10; 20; 01; G(ℤ_{3} × ℤ_{2}); ≅; 0; 5; 1; 2; 4; 3; G(ℤ_{6})]

Figure 2. The unit graphs of two isomorphic rings.

It is also easy to see that if the rings R_{1}, R_{2}, S_{1} and S_{2} are such that G(R_{1}) ≅ G(R_{2}) and G(S_{1}) ≅ G(S_{2}), then G(R_{1} × S_{1}) ≅ G(R_{2} × S_{2}). However, this property does not hold in general for other widely studied graphs associated to rings (for example, the zero-divisor graphs).

In this paper, we derive several necessary conditions for the nonplanarity of the unit graphs of finite commutative rings with nonzero identity; in particular, we show that given any positive integer g, there exists only a finite number of finite commutative rings with nonzero identity whose unit graphs have genus g. Also, in analogy with the results in [17], we determine, up to isomorphism, all finite commutative rings with nonzero identity whose unit graphs are toroidal. It may be recalled here that the genus of a graph G, denoted by γ(G), is smallest nonnegative integer g such that the graph G can be embedded on the surface obtained by attaching g handles to a sphere. The graphs of genus 0 and 1 are called planar graphs and toroidal graphs respectively. For unexplained terminology and notations in this paper, we refer the reader to [8].

2. Some auxiliary results and the related concepts

In this section, we put together certain graph theoretical terminologies and some well-known results which have been used extensively in the forthcoming sections. Note that all graphs considered in this section are finite simple graphs, that is, graphs with finitely many vertices and without loops or multiple edges.

Let x and y be any two vertices in a graph G. Then, x and y are said to be adjacent in G if x ≠ y and there is an edge {x, y} between x and y. A path between x and y is a sequence {x, x_{1}}, {x_{1}, x_{2}}, …, {x_{n}, y} of distinct edges, which is also written as {x, x_{1}, x_{2}, …, x_{n}, y}, where the vertices x, x_{1}, x_{2}, …, x_{n}, y are all distinct (except, possibly, x and y). A path between x and y is called a cycle if x = y. The number of edges in a path or a cycle, is called its length.

A graph G is said to be connected if there is a path between every pair of distinct vertices in G. A chord of a cycle in a graph is an edge of the graph which does not lie in the edge set of the cycle but whose endpoints lie in the vertex set of the cycle. A chordless cycle of a graph is a cycle without any chord.

A cycle of a graph, embedded on a surface, is called contractible with respect to the embedding if it can be contracted continuously on the surface to a point. A cycle of a toroidal graph is said to be flat if it is contractible in every torus embedding of the graph. Given a cycle C of a graph G, we write G − C to denote the graph obtained from G by deleting the vertices of C and the edges of the graph incident to the vertices of C.

A graph G is said to be complete if there is an edge between every pair of distinct vertices in G. We denote the complete graph with n vertices by K_{n}. A bipartite graph is the one whose vertex set can be partitioned into two disjoint parts in such a way that the two end vertices of every edge lie in different parts. Among the bipartite graphs, the complete bipartite graph is the one in which two vertices are adjacent if and only if they lie in different parts. The complete bipartite graph, with parts of size m and n, is denoted by K_{m,n}.

A subdivision of an edge {x, y} in a graph is a path {x, x_{1}, x_{2}, …, x_{n}, y} obtained by inserting some new vertices x_{1}, x_{2}, …, x_{n} into the edge {x, y}. A subdivision of a graph G is the result of some subdivisions of the edges of G. Furthermore, every graph can be considered as a subdivision of itself. A remarkably simple characterization of planar graphs was given by Kuratowski in 1930. Kuratowski’s theorem [8, Page 153] says that a graph is planar if and only if it contains no subdivision of K_{3,3} or K_{5}. As a consequence of Kuratowski’s theorem, one has the following result.

Lemma 2.1 ([19], Theorem 2.1). If a cycle C of a toroidal graph G is such that G−C is nonplanar, then C is flat in G. Furthermore, if flat C is chordless and G − C is connected, then C is a flat face in any torus embedding of G.

Given a graph G, we denote its vertex set by V (G) and its edge set by E(G). If G_{1} and G_{2} are any two graphs, then their disjoint union, denoted by G_{1} ⊔ G_{2}, is defined to be the graph in which the vertex set is V (G_{1}) ⊔ V (G_{2}) and the edge set is E(G_{1}) ⊔ E(G_{2}). The following result, which follows from [6, Corollary 2], often enables us to reformulate some results which are otherwise true for connected graphs.

Lemma 2.2. If a graph G is isomorphic to the disjoint union G_{1} ⊔ G_{2} of two graphs G_{1} and G_{2}, then γ(G) = γ(G_{1}) + γ(G_{2}).

If G is a graph and x ∈ V (G), then the degree of x in G is defined as the number of vertices adjacent to x in G, and is denoted by deg(x). If r is a nonnegative integer such that deg(x) = r for all x ∈ V (G), then the graph G is said to be r-regular. In general, we write δ(G) to denote the minimum of the degrees of the vertices of G. In this connection, using Lemma 2.2, one may reformulate [22, Proposition 2.1] as follows.

Lemma 2.3. If G is a graph (not necessarily connected) having n vertices with n ≥ 3, then

δ(G) ≤ 6 + \frac{12(γ(G) − 1)}{n}.

The girth of a graph G is the minimum of the lengths of all cycles in G, and is denoted by gr(G). If G is acyclic, that is, if G has no cycles, then we write gr(G) = ∞. It has been proved in [4, Section 2.3] that if G is a connected graph (but not acyclic) having n vertices and m edges, then

γ(G) ≥ \frac{m(k − 2)}{2k} − \frac{n}{2} + 1,

where k = gr(G). Therefore, using the facts that in an acyclic graph the total number of edges is less than the total number of vertices, and that the girth of a bipartite graph (which is not acyclic) is at least four, we have, in view of Lemma 2.2, the following result.

Lemma 2.4. If G is a bipartite graph (not necessarily connected) having n vertices and m edges with n ≥ 3, then

γ(G) ≥ \frac{m}{4} − \frac{n}{2} + 1.

We conclude the section with two useful results.

Lemma 2.5 ([21], Theorem 6–38). If n ≥ 3, then

γ(K_{n}) = ⌈\frac{(n − 3)(n − 4)}{12}⌉ .

Lemma 2.6 ([21], Theorem 6–37). If m, n ≥ 2, then

γ(K_{m,n}) = ⌈\frac{(m − 2)(n − 2)}{4}⌉ .

3. Some necessary conditions for the nonplanarity of unit graphs

In this section, we derive a few necessary conditions for the nonplanarity of the unit graphs of finite commutative rings with nonzero identity. However, we begin with a known result.

Lemma 3.1 ([5], Proposition 2.4). Let R be a finite commutative ring with nonzero identity, and U(R) be the set of all unit elements of R. Let x ∈ R. Then

deg(x) = \begin{cases}|U(R)| − 1 & if x ∈ U(R) and 2 ∈ U(R), \\ |U(R)| & otherwise. \end{cases}

Let us now derive the first necessary condition for the nonplanarity of unit graphs.

Proposition 3.2. Let R be a finite commutative ring with nonzero identity such that γ(G(R)) = g > 0. Then either |R| ≤ 12(g − 1) or |U(R)| ≤ 7.

Proof. If |R| > 12(g − 1), then, using Lemma 2.3, we deduce that

δ(G(R)) ≤ 6 + \frac{12(g − 1)}{|R|} < 6 + 1 = 7.

Since δ(G(R)) is an integer, we have δ(G(R)) ≤ 6. Hence, it follows from Lemma 3.1 that |U(R)| ≤ 7. □

Let R be a finite commutative ring with nonzero identity. Let Z(R) denote the set of all zero-divisors of R. It is easy to see that U(R)⊔Z(R) = R and so |U(R)|+|Z(R)| = |R|. The structure theorem for finite commutative rings says that R is isomorphic to a direct product of finite commutative local rings with nonzero identity, and such a product is unique up to the order in which the factors are arranged (see [18]). If R itself is a local ring, then we have the following result which is essentially due to Raghavendran.

Lemma 3.3 ([20], Theorem 2). Let R be a finite commutative local ring with nonzero identity. Then |R| = p^{nr}, |Z(R)| = p^{(n−1)r} and |U(R)| = p^{(n−1)r}(p^{r} − 1) for some prime p and some positive integers n and r.

Now, Lemma 3.3 together with some well-known results on the structures of small local rings (see, for example, [9, 10]) enable us to obtain the following result.

Proposition 3.4. Let R be a finite commutative local ring with nonzero identity such that |U(R)| ≤ 7. Then the possible forms of R are given by Table 1.

\begin{matrix}|U(R)| & |Z(R)| & |R| & R \\ 7 & 1 & 8 & 𝔽_{8} \\ 6 & 1 & 7 & ℤ_{7} \\ 6 & 3 & 9 & ℤ_{9}, \frac{ℤ_{3}[x]}{⟨x^{2}⟩} \\ 4 & 1 & 5 & ℤ_{5} \\ 4 & 4 & 8 & ℤ_{8}, \frac{ℤ_{2}[x]}{⟨x^{3}⟩}, \frac{ℤ_{2}[x]}{⟨2x,x^{2}−2⟩}, \frac{ℤ_{2}[x,y]}{⟨x,y⟩^{2}}, \frac{ℤ_{4}[x]}{⟨2,x⟩^{2}} \\ 3 & 1 & 4 & 𝔽_{4} \\ 2 & 1 & 3 & ℤ_{3} \\ 2 & 2 & 4 & ℤ_{4}, \frac{ℤ_{2}[x]}{⟨x^{2}⟩} \\ 1 & 1 & 2 & ℤ_{2} \end{matrix}

Table 1. Finite commutative local rings with at most 7 units.

As a consequence of the above result, we derive a necessary condition for the nonplanarity of the unit graphs of finite commutative local rings with nonzero identity.

Corollary 3.5. Let R be a finite commutative local ring with nonzero identity such that γ(G(R)) = g > 0. Then |R| ≤ max{9, 12(g − 1)}. In particular, the number of finite commutative local rings with nonzero identity such that γ(G(R)) = g > 0 is finite.

Proof. If |R| ≤ 12(g − 1), then we are done. Otherwise, by Proposition 3.2, we have |U(R)| ≤ 7. Therefore, by Proposition 3.4, |R| ≤ 9. This completes the proof of the first part. The last part of the corollary is obvious, because, given any positive integer g, the number of rings R with |R| ≤ max{9, 12(g − 1)} is clearly finite. □

In Figure 1, one can see that G(ℤ_{2} × ℤ_{2}) is isomorphic to the disjoint union of two copies of G(ℤ_{2}). In fact, it is not difficult to make a more general observation that if S is a finite commutative ring with nonzero identity, then the unit graph G(ℤ_{2} × ℤ_{2} × S) is isomorphic to the disjoint union of two copies of the unit graph G(ℤ_{2} × S). Therefore, in view of Lemma 2.2, we have the following result.

Lemma 3.6. Let S be a finite commutative ring with nonzero identity. Then we have γ(G(ℤ_{2} × ℤ_{2} × S)) = 2γ(G(ℤ_{2} × S)). In particular, γ(G((ℤ_{2})^{t})) = 0 for all t ≥ 1.

The following result plays an important role in getting rid of all finite commutative rings with nonzero identity whose unit graphs are planar.

Lemma 3.7 ([5], Theorem 5.14). Let R be a finite commutative ring with nonzero identity. Then the unit graph G(R) is planar if and only if R is isomorphic to one of ℤ_{5}, ℤ_{3} × ℤ_{3} or (ℤ_{2})^{t} × S, where t ≥ 0 and S is one of the rings ℤ_{2}, ℤ_{3}, ℤ_{4}, 𝔽_{4}

and \{ [ \begin{matrix}a & b \\ 0 & a \end{matrix}] | a, b ∈ ℤ_{2}\} ≅ \frac{ℤ_{2}[x]}{⟨x^{2}⟩}.

We are now in a position to state and prove the main result of this section.

Theorem 3.8. Let R be a finite commutative ring with nonzero identity such that γ(G(R)) = g > 0. Then either |R| ≤ 12(g − 1) or R ≅ (ℤ_{2})^{t} × S, where 0 ≤ t ≤ 1 + log_{2}g and S is one of the finite rings given by Table 2.

|U(R)|  S
7  𝔽_{8}
6  ℤ_{7}, ℤ_{9}, \frac{ℤ_{3}[x]}{⟨x^{2}⟩}, ℤ_{3} × 𝔽_{4}, ℤ_{4} × 𝔽_{4}, \frac{ℤ_{2}[x]}{⟨x^{2}⟩} × 𝔽_{4}
4  ℤ_{5} (for t ≠ 0), ℤ_{8}, \frac{ℤ_{2}[x]}{⟨x^{3}⟩}, \frac{ℤ_{2}[x]}{⟨2x,x^{2}−2⟩}, \frac{ℤ_{2}[x,y]}{⟨x,y⟩^{2}}, \frac{ℤ_{4}[x]}{⟨2,x⟩^{2}} , ℤ_{3} × ℤ_{3} (for t ≠ 0),
ℤ_{3} × ℤ_{4}, ℤ_{3} × \frac{ℤ_{2}[x]}{⟨x^{2}⟩}, ℤ_{4} × ℤ_{4}, ℤ_{4} × \frac{ℤ_{2}[x]}{⟨x^{2}⟩}, \frac{ℤ_{2}[x]}{⟨x^{2}⟩} × \frac{ℤ_{2}[x]}{⟨x^{2}⟩}

Table 2. Possible seed rings for toroidal unit graphs.

Proof. Let |R| > 12(g − 1). In this case, Proposition 3.2 implies that |U(R)| ≤ 7. Using the structure theorem for finite commutative rings (see the discussion preceding Lemma 3.3) along with Lemma 3.6 and the fact that g > 0, we conclude that

R ≅ (ℤ_{2})^{t} × R_{1} × R_{2} × ⋯ × R_{k},

where 0 ≤ t ≤ 1 + log_{2}g, k ≥ 1 and each R_{i} is a finite commutative local ring with nonzero identity having at least three elements. Now, we have

|U(R)| = |U(R_{1} × R_{2} × ⋯ × R_{k})| = |U(R_{1})| × |U(R_{2})| × ⋯ × |U(R_{k})|.

Clearly, |U(R)| ≠ 1. Since |U(R)| ≤ 7, we have the following possibilities: (1) |U(R)| = p, where p = 2, 3, 5 or 7. In this case, we have k = 1 and |U(R_{1})| = p.

(2) |U(R)| = 6. In this case, either we have k = 1 and |U(R_{1})| = 6, or we have k = 2, |U(R_{1})| = 2 and |U(R_{2})| = 3.

(3) |U(R)| = 4. In this case, either we have k = 1 and |U(R_{1})| = 4, or we have

k = 2, |U(R_{1})| = 2 and |U(R_{2})| = 2. The result now follows from Proposition 3.4 and Lemma 3.7. □

As an immediate corollary, we have the following result.

Corollary 3.9. Let R be a finite commutative ring with nonzero identity such that γ(G(R)) = g > 0. Then |R| ≤ 32g. In particular, given any positive integer g, the number of finite commutative rings with nonzero identity such that γ(G(R)) = g is finite.

Proof. By Theorem 3.8, either |R| ≤ 12(g−1) or R ≅ (ℤ_{2})^{t}×S, where 0 ≤ t ≤ 1+log_{2}g and S is a ring with |S| ≤ 16. In the second case, |R| = 2^{t}|S| = 2^{t−1}(2|S|) ≤ 32g. Hence, it follows that |R| ≤ max{32g, 12(g −1)} = 32g. The last part of the corollary is obvious, because, given any positive integer g, the number of rings R with |R| ≤ 32g is clearly finite. □

4. Classification of rings with toroidal unit graphs

In this section, we determine, up to isomorphism, all finite commutative rings with nonzero identity whose unit graphs have genus one, that is, whose unit graphs are toroidal graphs.

Let R be a finite commutative ring with nonzero identity such that γ(G(R)) = 1. Then, by Theorem 3.8, R is isomorphic to either S or ℤ_{2} × S, where S is one of the finite rings mentioned in Table 2. There are 36 such possibilities for R, among which we single out the ones whose unit graphs have genus 1. For this purpose, the following result is very useful; in fact, in combination with Lemma 2.4, it helps in determining some lower bounds for the genus of the unit graphs of rings of the type ℤ_{2} × S, where S is a finite commutative ring with nonzero identity.

Lemma 4.1 ([5], Theorem 3.5). Let R be a finite commutative ring with nonzero identity, and 𝔪 be a maximal ideal of R such that R/𝔪 ≅ ℤ_{2}. Then the unit graph G(R) is a bipartite graph. Moreover, G(R) is a complete bipartite graph if and only if R is a local ring.

Let us now start the process of classification by looking at some toroidal unit graphs.

Proposition 4.2. γ(G(ℤ_{2} × ℤ_{5})) = 1.

Proof. By Lemma 3.7, we have γ(G(ℤ_{2} × ℤ_{5})) ≥ 1. But Figure 3 gives an embedding

[figure: 04; 04; 03; 02; 01; 00; 04; 04; 03; 02; 01; 00; 10; 10; 11; 12; 13; 14; c; c; b; b; a; a]

Figure 3. Embedding of the unit graph of ℤ_{2} × ℤ_{5} on a torus.

of the unit graph G(ℤ_{2} × ℤ_{5}) on a torus, and so γ(G(ℤ_{2} × ℤ_{5})) = 1. □

Proposition 4.3. γ(G(ℤ_{2} × ℤ_{3} × ℤ_{3})) = 1. Proof. By Lemma 3.7, we have γ(G(ℤ_{2} × ℤ_{3} × ℤ_{3})) ≥ 1. But Figure 4 gives an

[figure: 120; 100; 110; 002; 000; 001; 002; 000; 001; 022; 012; 020; 010; 021; 011; 120; 100; 110; 122; 102; 112; 121; 101; 111]

Figure 4. Embedding of the unit graph of ℤ_{2} × ℤ_{3} × ℤ_{3} on a torus. embedding of G(ℤ_{2} × ℤ_{3} × ℤ_{3}) on a torus, and so γ(G(ℤ_{2} × ℤ_{3} × ℤ_{3})) = 1. □ Proposition 4.4. γ(G(ℤ_{3} × ℤ_{4})) = γ(G(ℤ_{3} × \frac{ℤ_{2}[x]}{⟨x^{2}⟩})) = 1. Proof. By Lemma 3.7, we have γ(G(ℤ_{3} × ℤ_{4})) ≥ 1. But Figure 5 gives an embedding

[figure: 00; 23; 22; 12; 03; 21; 11; 11; 02; 01; 02; 13; 20; 13; 00; 23; 22; 12; 10]

Figure 5. Embedding of the unit graph of ℤ_{3} × ℤ_{4} on a torus.

of the unit graph G(ℤ_{3} × ℤ_{4}) on a torus, and so γ(G(ℤ_{3} × ℤ_{4})) = 1. On the other hand, since the unit graph G(ℤ_{4}) is isomorphic to the unit graph G(\frac{ℤ_{2}[x]}{⟨x^{2}⟩}), we have

G(ℤ_{3} × ℤ_{4}) ≅ G(ℤ_{3} × \frac{ℤ_{2}[x]}{⟨x^{2}⟩}).

This completes the proof. □

Proposition 4.5. If S is one of the rings ℤ_{7}, ℤ_{8}, \frac{ℤ_{2}[x]}{⟨x^{3}⟩}, \frac{ℤ_{2}[x]}{⟨2x,x^{2}−2⟩}, \frac{ℤ_{2}[x,y]}{⟨x,y⟩^{2}} and \frac{ℤ_{4}[x]}{⟨2,x⟩^{2}} , then γ(G(S)) = 1.

Proof. Note that the unit graph G(ℤ_{7}) can be regarded as a subgraph of K_{7}, and so, by Lemmas 2.5 and 3.7, we have γ(G(ℤ_{7})) = 1. On the other hand, each of the remaining rings is a local ring with 8 elements of which exactly 4 are zero-divisors, and so it follows from Lemma 4.1 that the associated unit graph of each of these rings is a complete bipartite graph, namely, K_{4,4}. The proof is now completed by Lemma 2.6. □

Next we look at some unit graphs which have genus more than 1.

Proposition 4.6. γ(G(ℤ_{2} × ℤ_{3} × ℤ_{4})) = γ(G(ℤ_{2} × ℤ_{3} × \frac{ℤ_{2}[x]}{⟨x^{2}⟩})) = 2.

Proof. It is not difficult to see that G(ℤ_{2} ×ℤ_{3} ×ℤ_{4}) is isomorphic to the disjoint union of two copies of G(ℤ_{3} × ℤ_{4}). Therefore, by Lemma 2.2 and Proposition 4.4, we have γ(G(ℤ_{2} × ℤ_{3} × ℤ_{4})) = 2. On the other hand, since the unit graph G(ℤ_{4}) is isomorphic to the unit graph G(\frac{ℤ_{2}[x]}{⟨x^{2}⟩}), we have

G(ℤ_{2} × ℤ_{3} × ℤ_{4}) ≅ G(ℤ_{2} × ℤ_{3} × \frac{ℤ_{2}[x]}{⟨x^{2}⟩}).

This completes the proof. □

Proposition 4.7. If S is one of the rings ℤ_{8}, \frac{ℤ_{2}[x]}{⟨x^{3}⟩}, \frac{ℤ_{2}[x]}{⟨2x,x^{2}−2⟩}, \frac{ℤ_{2}[x,y]}{⟨x,y⟩^{2}} and \frac{ℤ_{4}[x]}{⟨2,x⟩^{2}} , then γ(G(ℤ_{2} × S)) = 2. On the other hand, γ(G(ℤ_{2} × ℤ_{7})) ≥ 5.

Proof. In view of the proof of Proposition 4.5, one may note that, for each of the given choices of S, the unit graph G(ℤ_{2} × S) is isomorphic to the disjoint union of two copies of K_{4,4}. Hence, the first part follows from Lemmas 2.2 and 2.6.

For the second part, note that the unit graph G(ℤ_{2} × ℤ_{7}) is 6-regular with 14 vertices. Also, by Lemma 4.1, it is bipartite, and so it has 42 edges. Therefore, by Lemma 2.4, we have γ(G(ℤ_{2} × ℤ_{7})) ≥ 5. This completes the proof. □

Let us now recall that a subgraph H of a graph G is called a spanning subgraph if they have the same sets of vertices. A 1-regular spanning subgraph H of a graph G is called a perfect matching of G. Given a graph G with a subgraph H, we write G \ H to denote the subgraph of G in which the vertex set is V (G) and the edge set is E(G) \ E(H).

Proposition 4.8. γ(G(𝔽_{8})) = 2 and γ(G(ℤ_{2} × 𝔽_{8})) ≥ 7.

Proof. The unit graph G(𝔽_{8}) is isomorphic to K_{8}, and so, by Lemma 2.5, we have γ(G(𝔽_{8})) = 2. On the other hand, the unit graph G(ℤ_{2} × 𝔽_{8}) has 16 vertices, and, by Lemma 4.1, it is bipartite. In fact, this graph is isomorphic to the graph K_{8,8} \ M, where M is a perfect matching of K_{8,8}, and so it has 56 edges. Therefore, by Lemma 2.4, we have γ(G(ℤ_{2} × 𝔽_{8})) ≥ 7. □

Proposition 4.9. γ(G(ℤ_{3} × 𝔽_{4})) ≥ 2 and γ(G(ℤ_{2} × ℤ_{3} × 𝔽_{4})) ≥ 7. Proof. Note that the unit graph G := G(ℤ_{3} ×𝔽_{4}) is the union of two planar subgraphs plotted in Figure 6 which intersect at exactly four vertices, namely, 00, 01, 0a and 0a^{2} (indicated by bigger bullets). It is easy to see that the graph G has 12 vertices and 36 edges. Moreover, it is a 6-regular graph. Also, it is easy to see that it is not a planar graph, as it contains a subdivision of K_{5}, namely, {20, 21, 2a, 2a^{2}, 0a, 11, 0a^{2}, 20}.

[figure: 00; 1a^{2}; 01; 0a; 10; 0a^{2}; 11; 1a; 00; 2a^{2}; 01; 0a; 20; 0a^{2}; 21; 2a]

Figure 6. Two planar subgraphs of the unit graph of ℤ_{3} × 𝔽_{4}.

Let us now assume that G is toroidal, that is, γ(G) = 1. Then, by Euler’s formula, G has 36 − 12 = 24 faces. Also, note that G is symmetrical in nature. We use Lemma 2.1 to show that every 3-cycle C in G is a face, and arrive at a contradiction.

First, let us consider a 3-cycle having empty interior. By symmetry, it is enough to take C = {00, 1a^{2}, 1a, 00}. Then G − C is given as indicated in Figure 7. Clearly, G − C is nonplanar, as it contains a subdivision of K_{5}, namely, {20, 21, 2a, 2a^{2}, 0a, 11, 0a^{2}, 20}. Moreover, C is chordless and G − C is connected. Therefore, by Lemma 2.1, C is a face. Note that there are 24 such 3-cycles in G.

[figure: 01; 0a; 10; 0a^{2}; 11; 2a^{2}; 01; 0a; 20; 0a^{2}; 21; 2a]

Figure 7. The graph G(ℤ_{3} × 𝔽_{4}) − {00, 1a^{2}, 1a, 00}.

Next, we consider the 3-cycle C = {1a^{2}, 10, 1a, 1a^{2}}. Then G − C is given as indicated in Figure 8. Again, it is clear that G − C is nonplanar, as it contains a subdivision of K_{5}, namely, {20, 21, 2a, 2a^{2}, 0a, 11, 0a^{2}, 20}. Moreover, C is chordless and G − C is connected. Therefore, by Lemma 2.1, C is a face.

[figure: 00; 01; 0a; 0a^{2}; 11; 00; 2a^{2}; 01; 0a; 20; 0a^{2}; 21; 2a]

Figure 8. The graph G(ℤ_{3} × 𝔽_{4}) − {1a^{2}, 10, 1a, 1a^{2}}.

Since we have already found 25 faces, our assumption that G is toroidal is wrong. Hence, we conclude that γ(G(ℤ_{3} × 𝔽_{4})) ≥ 2.

For the second part, note that the unit graph G(ℤ_{2} × ℤ_{3} × 𝔽_{4}) is 6-regular with 24 vertices. Also, by Lemma 4.1, it is bipartite, and so it has 72 edges. Therefore, by Lemma 2.4, we have γ(G(ℤ_{2} × ℤ_{3} × 𝔽_{4})) ≥ 7. This completes the proof. □

Arguing in the same manner as above, we also have the following result.

Proposition 4.10. If S is one of the rings ℤ_{9} and \frac{ℤ_{3}[x]}{⟨x^{2}⟩}, then γ(G(S)) ≥ 2 and γ(G(ℤ_{2} × S)) ≥ 6.

Proof. Note that the unit graphs of the rings ℤ_{9} and \frac{ℤ_{3}[x]}{⟨x^{2}⟩} are isomorphic. Therefore, it is enough to prove the result only for ℤ_{9}. It is easy to see, from Figure 9, that the unit graph G(ℤ_{9}) is a nonplanar graph with 9 vertices and 24 edges. Moreover, the

Figure 9. The unit graph of ℤ_{9}. number of 3-cycles in it is 20. If C is one such 3-cycle, then it is easy to see that C is chordless, and G(ℤ_{9}) − C is connected and nonplanar. In fact, G(ℤ_{9}) − C is either a subdivision of K_{5} or has a subgraph isomorphic to K_{3,3}, depending on whether the 3-cycle C contains one or none of the vertices 0, 3 and 6. Therefore, if G(ℤ_{9}) is toroidal, then it follows from Lemma 2.1 that every 3-cycle in G(ℤ_{9}) is a face, and so G(ℤ_{9}) has at least 20 faces, whereas from Euler’s formula it follows that G(ℤ_{9}) has 15 faces. Hence, we have γ(G(ℤ_{9})) ≥ 2.

[figure: 1; 0; 2; 7; 6; 8; 4; 3; 5]

For the second part, note that the unit graph G(ℤ_{2} × ℤ_{9}) is 6-regular with 18 vertices. Also, by Lemma 4.1, it is bipartite, and so it has 54 edges. Therefore, by Lemma 2.4, we have γ(G(ℤ_{2} × ℤ_{9})) ≥ 6. This completes the proof. □

Proposition 4.11. If S is one of the rings ℤ_{4} × ℤ_{4}, ℤ_{4} × \frac{ℤ_{2}[x]}{⟨x^{2}⟩} and \frac{ℤ_{2}[x]}{⟨x^{2}⟩} × \frac{ℤ_{2}[x]}{⟨x^{2}⟩}, then γ(G(S)) = 2 and γ(G(ℤ_{2} × S)) = 4.

Proof. Consider the following two subsets of the vertex set of G(ℤ_{4} × ℤ_{4}):

V_{1} = {(0, 0), (0, 2), (2, 0), (2, 2), (1, 1), (1, 3), (3, 1), (3, 3)},
V_{2} = {(0, 1), (0, 3), (2, 1), (2, 3), (1, 0), (1, 2), (3, 0), (3, 2)}.

It is easy to see that the two subgraphs ⟨V_{1}⟩ and ⟨V_{2}⟩ are disjoint, and their union is G(ℤ_{4} × ℤ_{4}). Moreover, ⟨V_{1}⟩ ≅ ⟨V_{2}⟩ ≅ K_{4,4}. Therefore, it follows from Lemma 2.2 and Lemma 2.6 that γ(G(ℤ_{4} × ℤ_{4})) = 2. Also, it is easy to see that G(ℤ_{2} × ℤ_{4} × ℤ_{4}) is isomorphic to the disjoint union of two copies of G(ℤ_{4} × ℤ_{4}). Therefore, in view of Lemma 2.2, it follows that γ(G(ℤ_{2} × ℤ_{4} × ℤ_{4})) = 4. On the other hand, since the unit graph G(ℤ_{4}) is isomorphic to the unit graph G(\frac{ℤ_{2}[x]}{⟨x^{2}⟩}), we have

G(ℤ_{4} × ℤ_{4}) ≅ G(ℤ_{4} × \frac{ℤ_{2}[x]}{⟨x^{2}⟩}) ≅ G(\frac{ℤ_{2}[x]}{⟨x^{2}⟩} × \frac{ℤ_{2}[x]}{⟨x^{2}⟩})

and

G(ℤ_{2} × ℤ_{4} × ℤ_{4}) ≅ G(ℤ_{2} × ℤ_{4} × \frac{ℤ_{2}[x]}{⟨x^{2}⟩}) ≅ G(ℤ_{2} × \frac{ℤ_{2}[x]}{⟨x^{2}⟩} × \frac{ℤ_{2}[x]}{⟨x^{2}⟩}).

Hence, the result follows. □

Proposition 4.12. If S is one of the rings ℤ_{4} × 𝔽_{4} and \frac{ℤ_{2}[x]}{⟨x^{2}⟩} × 𝔽_{4}, then γ(G(S)) ≥ 2 and γ(G(ℤ_{2} × S)) ≥ 9.

Proof. Note that G(ℤ_{4}) is a spanning subgraph of G(𝔽_{4}). This implies that G(ℤ_{4}×ℤ_{4}) is an spanning subgraph of G(ℤ_{4} × 𝔽_{4}). Therefore, by Proposition 4.11, we have γ(G(ℤ_{4} ×𝔽_{4})) ≥ 2. Also note that the unit graph G(ℤ_{2} ×ℤ_{4} ×𝔽_{4}) is 6-regular with 32 vertices. Moreover, by Lemma 4.1, it is bipartite, and so it has 96 edges. Therefore, by Lemma 2.4, we have γ(G(ℤ_{2} × ℤ_{4} × 𝔽_{4})) ≥ 9. On the other hand, since the unit graph G(ℤ_{4}) is isomorphic to the unit graph G(\frac{ℤ_{2}[x]}{⟨x^{2}⟩}), we have

G(ℤ_{4} × 𝔽_{4}) ≅ G(\frac{ℤ_{2}[x]}{⟨x^{2}⟩} × 𝔽_{4})

and

G(ℤ_{2} × ℤ_{4} × 𝔽_{4}) ≅ G(ℤ_{2} × \frac{ℤ_{2}[x]}{⟨x^{2}⟩} × 𝔽_{4}).

This completes the proof. □

Let us now summarize what we have achieved so far: If S is a finite commutative ring with nonzero identity, then, with γ_{S} = γ(G(S)) and γ_{2S} = γ(G(ℤ_{2} × S)), one has Table 3.

\begin{aligned}S & γ_{S} & γ_{2S} \\ ℤ_{5}, ℤ_{3} × ℤ_{3} & 0 & 1 \\ ℤ_{3} × ℤ_{4}, ℤ_{3} × \frac{ℤ_{2}[x]}{⟨x^{2}⟩}, ℤ_{8}, \frac{ℤ_{2}[x]}{⟨x^{3}⟩}, \frac{ℤ_{2}[x]}{⟨2x,x^{2}−2⟩}, \frac{ℤ_{2}[x,y]}{⟨x,y⟩^{2}}, \frac{ℤ_{4}[x]}{⟨2,x⟩^{2}} & 1 & 2 \\ ℤ_{7} & 1 & ≥ 5 \\ 𝔽_{8} & 2 & ≥ 7 \\ ℤ_{3} × 𝔽_{4} & ≥ 2 & ≥ 7 \\ ℤ_{9}, \frac{ℤ_{3}[x]}{⟨x^{2}⟩} & ≥ 2 & ≥ 6 \\ ℤ_{4} × ℤ_{4}, ℤ_{4} × \frac{ℤ_{2}[x]}{⟨x^{2}⟩}, \frac{ℤ_{2}[x]}{⟨x^{2}⟩} × \frac{ℤ_{2}[x]}{⟨x^{2}⟩} & 2 & 4 \\ ℤ_{4} × 𝔽_{4}, \frac{ℤ_{2}[x]}{⟨x^{2}⟩} × 𝔽_{4} & ≥ 2 & ≥ 9 \end{aligned}

Table 3. Genus of some unit graphs.

Finally, using Table 3 and Theorem 3.8, one easily obtains the following classification theorem.

Theorem 4.13. Let R be a finite commutative ring with nonzero identity. Then the unit graph G(R) is a toroidal graph if and only if R is isomorphic to one of ℤ_{2} × ℤ_{5}, ℤ_{2} × ℤ_{3} × ℤ_{3}, ℤ_{3} × ℤ_{4}, ℤ_{3} × \frac{ℤ_{2}[x]}{⟨x^{2}⟩}, ℤ_{8}, \frac{ℤ_{2}[x]}{⟨x^{3}⟩}, \frac{ℤ_{2}[x]}{⟨2x,x^{2}−2⟩}, \frac{ℤ_{2}[x,y]}{⟨x,y⟩^{2}}, \frac{ℤ_{4}[x]}{⟨2,x⟩^{2}} or ℤ_{7}.

Acknowledgment

The authors are grateful to the anonymous referee for bringing to their notice an inadvertent omission in Theorem 3.8, for making many constructive suggestions, and for supplying some additional references.

References

[1] D. D. Anderson, M. Naseer, Beck’s coloring of a commutative ring, J. Algebra 159 (1993), no. 2, 500–514.

[2] D. F. Anderson, M. C. Axtell, J. A. Stickles, Zero-divisor graphs in commutative rings, Commutative Algebra, Noetherian and non-Noetherian Perspectives, 23–45, Springer, New York, 2011.

[3] D. F. Anderson, P. S. Livingston, The zero-divisor graph of a commutative ring, J. Algebra 217 (1999), no. 2, 434–447.

[4] D. Archdeacon, Topological graph theory: a survey, Surveys in graph theory (San Francisco, CA, 1995), Congr. Numer. 115 (1996), 5–54.

[5] N. Ashrafi, H. R. Maimani, M. R. Pournaki, S. Yassemi, Unit graphs associated with rings, Comm. Algebra 38 (2010), no. 8, 2851–2871.

[6] J. Battle, F. Harary, Y. Kodama, J. W. T. Youngs, Additivity of the genus of a graph, Bull. Amer. Math. Soc. 68 (1962), 565–568.

[7] I. Beck, Coloring of commutative rings, J. Algebra 116 (1988), no. 1, 208–226.

[8] G. Chartrand, O. R. Oellermann, Applied and Algorithmic Graph Theory, McGraw-Hill, Inc., New York, 1993.

[9] B. Corbas, G. D. Williams, Rings of order p^{5}, I. Nonlocal rings, J. Algebra 231 (2000), no. 2, 677–690.

[10] B. Corbas, G. D. Williams, Rings of order p^{5}, II. Local rings, J. Algebra 231 (2000), no. 2, 691–704.

[11] R. P. Grimaldi, Graphs from rings, Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1989), Congr. Numer. 71 (1990), 95–103.

[12] H. R. Maimani, M. R. Pournaki, A. Tehranian, S. Yassemi, Graphs attached to rings revisited, Arab. J. Sci. Eng. 36 (2011), no. 6, 997–1011.

[13] H. R. Maimani, M. R. Pournaki, S. Yassemi, A class of weakly perfect graphs, Czechoslovak Math. J. 60(135) (2010), no. 4, 1037–1041.

[14] H. R. Maimani, M. R. Pournaki, S. Yassemi, Rings which are generated by their units: a graph theoretical approach, Elem. Math. 65 (2010), no. 1, 17–25.

[15] H. R. Maimani, M. R. Pournaki, S. Yassemi, Weakly perfect graphs arising from rings, Glasg. Math. J. 52 (2010), no. 3, 417–425.

[16] H. R. Maimani, M. R. Pournaki, S. Yassemi, Necessary and sufficient conditions for unit graphs to be Hamiltonian, Pacific J. Math. 249 (2011), no. 2, 419–429.

[17] H. R. Maimani, C. Wickham, S. Yassemi, Rings whose total graphs have genus at most one, Rocky Mountain J. Math. 42 (2012), no. 5, 1551–1560.

[18] B. R. McDonald, Finite Rings with Identity, Pure and Applied Mathematics, vol. 28, Marcel Dekker, Inc., New York, 1974.

[19] E. Neufeld, W. Myrvold, Practical toroidality testing, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans, LA, 1997), 574–580, ACM, New York, 1997.

[20] R. Raghavendran, Finite associative rings, Composito Math. 21 (1969), no. 2, 195–229.

[21] A. T. White, Graphs, Groups and Surfaces, North-Holland Mathematics Studies, no. 8., North-Holland, Amsterdam, 1973.

[22] C. Wickham, Classification of rings with genus one zero-divisor graphs, Comm. Algebra 36 (2008), no. 2, 325–345.

A. K. Das, Department of Mathematics, North-Eastern Hill University, Permanent Campus, Shillong-793022, Meghalaya, India.

E-mail address: akdasnehu@gmail.com

H. R. Maimani, Mathematics Section, Department of Basic Sciences, Shahid Rajaee Teacher Training University, P.O. Box 16785-163, Tehran, Iran, and School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran.

E-mail address: maimani@ipm.ir

M. R. Pournaki, Department of Mathematical Sciences, Sharif University of Technology, P.O. Box 11155-9415, Tehran, Iran, and School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran.

E-mail address: pournaki@ipm.ir
URL: http://math.ipm.ac.ir/∼pournaki/

S. Yassemi, School of Mathematics, Statistics and Computer Science, College of Science, University of Tehran, Tehran, Iran, and School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran.

E-mail address: yassemi@ipm.ir
URL: http://math.ipm.ac.ir/∼yassemi/