GRAPHS ATTACHED TO RINGS REVISITED

H. R. MAIMANI, M. R. POURNAKI, A. TEHRANIAN, AND S. YASSEMI

Abstract. In this paper, we discuss some recent results on graphs attached to rings. In particular, we deal with comaximal graphs, unit graphs, and total graphs. We then define the notion of cototal graph and, using this graph, we characterize the rings which are additively generated by their zero divisors. Finally, we glance at graphs attached to other algebraic structures.

1. Introduction

Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra in various combinatorial contexts and vise versa. Associating a graph with an algebraic structure is a research subject in this area and has attracted considerable attention. In fact, research in this subject aims at exposing the relationship between algebra and graph theory and at advancing applications of one to the other. The story goes back to a paper of Beck [8] in 1988, where he introduced the idea of a zerodivisor graph of a commutative ring R with identity. He defined Γ_{0}(R) to be the graph whose vertices are elements of R and in which two vertices x and y are adjacent if and only if xy = 0. He was mostly concerned with coloring Γ_{0}(R). Let χ(R) and ω(R) denote the chromatic number and the clique number of Γ_{0}(R), respectively. Beck conjectured that χ(R) = ω(R). Such graphs are called weakly perfect graphs. This investigation of coloring of a commutative ring was then continued by Anderson and Naseer [2]. They gave a counterexample to the above conjecture of Beck. A different method of associating a zero-divisor graph to a commutative ring R was proposed by Anderson and Livingston [5]. They believed that this better illustrated the zerodivisor structure of the ring. They defined Γ(R) to be the graph whose vertices are nonzero zero divisors of R and in which two vertices x and y are adjacent if and only if xy = 0. This graph is defined slightly differently than the graph introduced by Beck who took the set of vertices to be all of R. For a survey and recent results concerning zero-divisor graphs, we refer the reader to [3].

2000 Mathematics Subject Classification. 05C15, 05C17, 05C38, 05C40, 05C45, 05C69, 05C75, 11A25, 13A10, 13A15, 13M05, 16U60.

Key words and phrases. Chromatic index, Chromatic number, Clique number, Comaximal graph, Connectedness, Cototal graph, Counit graph, Diameter, Finite ring, Girth, Hamiltonian cycle, Hamiltonian graph, Planarity, Total graph, Unit element, Unit graph, Weakly perfect graph, Zerodivisor graph.

The research of H. R. Maimani was in part supported by a grant from IPM (No. 89050211).

The research of M. R. Pournaki was in part supported by a grant from the Academy of Sciences for the Developing World (TWAS–UNESCO Associateship – Ref. FR3240126591). The research of A.

Tehranian was in part supported by a grant from Islamic Azad University (IAU). The research of S.

Yassemi was in part supported by a grant from the University of Tehran.

One can associate other graphs to rings or other algebraic structures. The benefit of studying these graphs is that one may find some results about the algebraic structures and vise versa. 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 structures and the corresponding graphs. This is a particularly interesting subject for some graph theorists and algebraists, since it relates two very different areas of mathematics, involves fun computations, and can be studied at many different levels of mathematical expertise and sophistication.

In this survey, we discuss some recent results on graphs attached to rings. In particular, we deal with comaximal graphs, unit graphs, and total graphs. We then define the notion of cototal graph and using this graph we characterize the rings which are additively generated by their zero divisors. Finally, we glance at graphs attached to other algebraic structures.

In what follows, all rings are associative with nonzero identity, which is preserved by ring homomorphisms and inherited by subrings. Also, throughout the paper, by a graph we mean a finite undirected graph without loops or multiple edges.

2. Comaximal graphs

Let G be a graph. A k-coloring of the vertices of G is an assignment of k colors to the vertices of G in such a way that no two adjacent vertices receive the same color. The chromatic number of G, denoted by χ(G), is the smallest number k such that G admits a k-coloring. A clique in G is a set of pairwise adjacent vertices of G. A clique of maximum size is called a maximum clique. The clique number of G, denoted by ω(G), is the number of vertices of a maximum clique in G. The parameters χ(G) and ω(G) have been extensively studied by many authors. Nevertheless, finding the chromatic number and the clique number of a graph is long known to be an NP-hard problem (cf. [12]). A graph G is called weakly perfect provided χ(G) = ω(G). It is known that deciding whether χ(G) = ω(G) is an NP-complete problem (cf. [26]).

2.1. Comaximal graphs: definition and remarks. Let R be a commutative ring and let J(R) denote the Jacobson radical of R. In 1995, Sharma and Bhatwadekar [32] introduced the comaximal graph of R, denoted by Γ(R), which is the graph obtained by setting all the elements of R to be the vertices and defining distinct vertices x and y to be adjacent if and only if Rx + Ry = R. It is easy to see that the unit elements of R are adjacent to all elements of R, while all elements of J(R) are adjacent only to the unit elements. In [32], the authors have proved that χ(R) < ∞ if and only if R is a finite ring, and in this case, they have shown that the graph is weakly perfect. In fact, they showed that χ(R) = ω(R) = t + ℓ, where t and ℓ denote the number of maximal ideals of R and the number of unit elements of R, respectively. Later, Maimani et al. [24] studied Γ(R) and its two subgraphs Γ_{1}(R) and Γ_{2}(R), which are induced by the unit elements and the nonunit elements of R, respectively.

2.2. Basic properties of comaximal graphs. For r a nonnegative integer, an rpartite graph is one whose vertex set is partitioned into r disjoint parts in such a way that the two end vertices for each edge lie in distinct partitions. A complete r-partite graph is one in which each vertex is joined to every vertex that is not in the same partition. The (complete) two-partite graph is called the (complete) bipartite graph. The complete bipartite graph with exactly two partitions of size m and n is denoted by K_{m,n}, and K_{1,1} is called the star graph.

For a graph G, let V (G) denote the set of vertices, and let E(G) denote the set of edges. Let G be graph, and suppose x, y ∈ V (G). We recall that a walk between x and y is a sequence x = v_{0}, e_{1}, v_{1}, …, e_{k}, v_{k} = y of vertices and edges of G, denoted by

x = v_{0} ⟶^{e_{1}} v_{1} ⟶ ⋯ ⟶^{e_{k}} v_{k} = y,

such that for every i with 1 ≤ i ≤ k, the edge e_{i} has endpoints v_{i−1} and v_{i}. Also, a path between x and y is a walk between x and y without repeated vertices. A trail between x and y is a walk between x and y in which all the edges are distinct. A graph G is called connected if for any vertices x and y of G there is a path between x and y. Otherwise, G is called disconnected. A graph G is said to be totally disconnected if E(G) = ∅. For a graph G and vertices x and y of G, the distance between x and y, denoted by d(x, y), is the number of edges in a shortest path between x and y. If there is no path between x and y, then we write d(x, y) = ∞. The largest distance among all distances between pairs of the vertices of a graph G is called the diameter of G and is denoted by diam(G).

In the following, we denote the set of maximal ideals of the ring R by Max(R). Note that in Theorem 2.2(b), Theorem 2.3, and the last part of Theorem 2.4, the assertion |Max(R)| ≥ 2 has an important role and without it the results are wrong. Unfortunately, this assertion missed the point in the statement of Theorem 2.2(b) in the published version (cf. [24, Proposition 2.3]).

Theorem 2.1 ([24], Theorem 2.2). Let R be a commutative ring. Then the following statements are equivalent:

(a) The graph Γ_{2}(R) \ J(R) is complete bipartite.

(b) |Max(R)| = 2.

Theorem 2.2 ([24], Proposition 2.3). Let R be a commutative ring and let n > 1. Then the following statements hold:

(a) If |Max(R)| = n < ∞, then the graph Γ_{2}(R) \ J(R) is n-partite.

(b) If |Max(R)| ≥ 2 and the graph Γ_{2}(R) \ J(R) is n-partite, then |Max(R)| ≤ n. In this case, if the graph Γ_{2}(R)\J(R) is not (n−1)-partite, then |Max(R)| = n.

Theorem 2.3 ([24], Proposition 2.4). Let R be a commutative ring with |Max(R)| ≥ 2. Then the following statements hold:

(a) If the graph Γ_{2}(R) \ J(R) is complete n-partite, then n = 2.

(b) If there exists a vertex of the graph Γ_{2}(R)\J(R), which is adjacent to its every other vertex, then R ≅ ℤ_{2} × F, where F is a field.

Theorem 2.4 ([24], Theorem 3.1, Lemma 3.2, and Proposition 3.3). Let R be a commutative ring. Then the graph Γ_{2}(R)\J(R) is connected and we have diam(Γ_{2}(R)\ J(R)) ≤ 3. Moreover, diam(Γ_{2}(R) \ J(R)) = 1 if and only if R ≅ ℤ_{2} × ℤ_{2}. Also if |Max(R)| ≥ 2, then diam(Γ_{2}(R) \ J(R)) = 2 if and only if one of the following statements hold:

(a) The Jacobson radical J(R) is a prime ideal of R.

(b) |Max(R)| = 2 and R ≇ ℤ_{2} × ℤ_{2}.

A ring R is called clean if every element of R is the sum of an idempotent and a unit, and R is called uniquely clean if this representation is unique (cf. [1, 28]). This definition dates back to 1977 when it was introduced by Nicholson [28]. For example, quasi-local rings are clean. The following result gives an application of Sharma-Bhatwadekar graph to characterize clean rings.

Theorem 2.5 ([24], Theorem 2.5). Let R be a commutative ring. Then the following statements are equivalent:

(a) The ring R is a finite product of quasi-local rings.

(b) The ring R is clean and ω(Γ_{2}(R) \ J(R)) is finite.

Theorem 2.6 ([24], Theorem 4.4). Let {(R_{i}, 𝔪_{i})}_{i=1}^{m} and {(S_{j}, 𝔫_{j})}_{j=1}^{n} be two families of finite commutative quasi-local rings and let R = R_{1}×⋯×R_{m} and S = S_{1}×⋯×S_{n}. If Γ(R) ≅ Γ(S), then we have m = n and there is a permutation σ on the set {1, 2, …, m} such that |R_{i}/𝔪_{i}| = |S_{σ(i)}/𝔫_{σ(i)}| and R_{i}/𝔪_{i} ≅ S_{σ(i)}/𝔫_{σ(i)}, for every i = 1, …, m. In particular, if Γ(R) ≅ Γ(S) and every R_{i} is a finite field, then R ≅ S.

In addition, Maimani et al. in Proposition 4.7. of [24] have claimed that for given rings R and S, Γ(R) ≅ Γ(S) implies that R/J(R) ≅ S/J(S), where J(R) and J(S) denote the Jacobson radical of the rings R and S, respectively. In the case that the rings R and S are finite, this result indeed follows from Theorem 2.6 (cf. [24, Theorem 4.4]), but in general this is not true. The authors would like to thank S. M. Moconja and Z. Z. Petrović for pointing this out and giving a counterexample (cf. [27, Example 4.1]).

A cycle of a graph is a path such that the start and end vertices are the same. The number of edges in a cycle is called its length. For a graph G, the girth of G is the length of a shortest cycle in G and is denoted by gr(G). If G has no cycles, we define the girth of G to be infinite, and in this case, G is called a forest. A connected graph is Eulerian if there exists a closed trail containing every edge.

Theorem 2.7 ([33], Theorem 3.5). Let R be a commutative ring. Then the following are equivalent for Γ_{2}(R) \ J(R):

(i) Γ_{2}(R) \ J(R) is a forest.

(ii) Γ_{2}(R) \ J(R) is either totally disconnected or a star graph.

(iii) R is either a local ring which is not a field or R is isomorphic to ℤ_{2} ×F, where F is a field.

Theorem 2.8 ([33], Theorem 3.10). Let R ≅ R_{1}×R_{2}×⋯×R_{k} be a finite commutative ring, where R_{i} is a finite local ring for every i and k ≥ 2. Then the following are equivalent:

(i) Γ_{2}(R) \ J(R) is Eulerian.

(ii) R ≇ ℤ_{2} × ⋯ × ℤ_{2} and R ≇ R_{1} × ⋯ × R_{t} × ℤ_{2} × ⋯ × ℤ_{2}, where |R_{i}| is odd

for i ≤ t and 1 ≤ t < k. (iii) |R_{i}| = 2r with r ≥ 2 for some i, or |R_{i}| is odd for every i.

A graph G is said to be planar if it can be drawn in the plane in such a way that its edges intersect only at their ends. In the following theorem, 𝔽_{4} denotes the field with four elements.

Theorem 2.9 ([33], Corollary 5.3). Let R be a finite commutative ring. Then Γ(R) is planar if and only if R is isomorphic to one of the following rings: ℤ_{2}, ℤ_{3}, ℤ_{4}, ℤ_{2}[x]/(x^{2}), 𝔽_{4}, ℤ_{2} × ℤ_{2}, ℤ_{2} × ℤ_{3}, and ℤ_{2} × ℤ_{2} × ℤ_{2}.

It is also shown that the clique number of Γ_{2}(R) is equal to the number of maximal ideals of R (cf. [33]). In addition, Wang [34] considered the comaximal graph Γ(R) of a not necessarily commutative ring R. He showed that if R is Artinian, then Γ(R)\J(R) is connected. Also, for R the full ring of all n × n matrices over a finite field F, the minimal degree, maximal degree, clique number, connectivity and chromatic number of Γ(R) are computed. For a short survey concerning zero-divisor graphs, as well as comaximal graphs, we refer the reader to [31].

3. The story behind unit graphs

Let p be a prime number and let k be a positive integer. A while ago, we (H. R. Maimani, M. R. Pournaki, and S. Yassemi) defined a graph, denoted by G(p^{k}), based on positive integers and their sums. The vertices of G(p^{k}) are the elements of {1, …, p^{k}} and distinct vertices x and y are defined to be adjacent if and only if gcd(x + y, p) = 1. We then proved that the class of these graphs is a new class of weakly perfect graphs. More precisely, we showed that for a given prime number p and for a positive integer k, the graph G(p^{k}) is a weakly perfect graph (cf. [20, Theorem 2.1]). Moreover, we proved that

χ(G(p^{k})) = ω(G(p^{k})) = \{ \begin{matrix}2 & if p = 2, \\ p^{k−1}(p − 1)/2 + 1 & if p > 2. \end{matrix}

After a while, we realized that these graphs have been already included in a paper of Grimaldi [14]. He has denoted these graphs by G(ℤ_{p^{k}}) instead of G(p^{k}) and has found some of their properties. Let n be a positive integer, and let ℤ_{n} be the ring of integers modulo n. In 1989, Grimaldi defined a graph G(ℤ_{n}) based on the elements and units of ℤ_{n}. The vertices of G(ℤ_{n}) are the elements of ℤ_{n}; distinct vertices x and y are defined to be adjacent if and only if x + y is a unit of ℤ_{n}. For a positive integer m, it follows that G(ℤ_{2m}) is a φ(2m)-regular graph, where φ is the Euler phi function. In case m ≥ 2, G(ℤ_{2m}) can be expressed as the union of φ(2m)/2 Hamiltonian cycles, i.e., cycles containing all the vertices of the graph. The odd case is not quite so easy, but the structure is clear and the results are similar to the even case. We recall that a cone over a graph is obtained by taking the categorical product of the graph and a path with a loop at one end, and then identifying all the vertices whose second coordinate is the other end of the path. When p is an odd prime, G(ℤ_{p}) can be expressed as a cone over a complete partite graph with (p − 1)/2 partitions of size two. This leads to an explicit formula for the chromatic polynomial p(t) of G(ℤ_{p}). Here, p(t) is the number of ways needed to color the vertices of G(ℤ_{p}) using at most t colors in such a way that no two adjacent vertices receive the same color. The chromatic polynomial of a graph was introduced by Birkhoff in 1912 to study the four-color problem (cf. [9]). The article [14] also concludes with some properties of the graphs G(ℤ_{p^{k}}), where p is a prime number and k ≥ 2.

Based on that mentioned above, we decided to generalize G(ℤ_{n}) to G(R), the unit graph of R, where R is an arbitrary associative ring with nonzero identity. This graph is a subgraph of the comaximal graph studied in Sect. 2 (also cf. [24]). But a question may occur: what is the benefit of the unit graphs? We showed that the unit graphs associated with rings can play a role in the study of rings. In fact, by using unit graphs, we characterized the rings which are generated by their units (cf. [21, Theorem 1.1]). More precisely, let R be a finite commutative ring with nonzero identity. Then R is generated by its units if and only if R cannot have ℤ_{2} × ℤ_{2} as a quotient. As a byproduct, if R is generated by its units, then every element of R can be written as a sum of at most three units.

3.1. Unit graphs: definition and remarks. Let R be a ring and U(R) be the set of unit elements of R. The unit graph of R, denoted by G(R), is the graph obtained by setting all the elements of R to be the vertices and defining distinct vertices x and y to be adjacent if and only if x + y ∈ U(R). If we omit the word distinct, we obtain the closed unit graph denoted by \overline{G}(R); this graph may have loops. Note that if 2 ∉ U(R), then \overline{G}(R) = G(R).

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

Figure 1. The unit graphs of some specific rings

It is easy to see that, for given rings R and S, if R ≅ S as rings, then G(R) ≅ G(S) as graphs. This point is illustrated in Fig. 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

3.2. Basic properties of unit graphs. Let G_{1} and G_{2} be two vertex-disjoint graphs. The category product of G_{1} and G_{2} is denoted by G_{1} ˙×G_{2}. That is, V (G_{1} ˙×G_{2}) := V (G_{1}) × V (G_{2}); two distinct vertices (x, y) and (x′, y′) are adjacent if and only if x is adjacent to x′ in G_{1} and y is adjacent to y′ in G_{2}. Clearly, we have \overline{G}(R_{1}) ˙×\overline{G}(R_{2}) ≅ G(R_{1} × R_{2}). In Fig. 3, we illustrate the above point for the direct product of ℤ_{2} and ℤ_{3}.

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

Figure 3. The category product of two closed unit graphs

For a graph G and vertex x ∈ V (G), the degree of x, denoted by deg(x), is the number of edges of G incident with x. For a nonnegative integer r, the graph G is called r-regular if the degree of each vertex of G is equal to r.

Theorem 3.1 ([6], Proposition 2.4). Let R be a finite ring. Then the following statements hold for the unit graph of R:

(a) If 2 ∉ U(R), then the unit graph G(R) is a |U(R)|-regular graph.

(b) If 2 ∈ U(R), then for every x ∈ U(R) we have deg(x) = |U(R)| − 1, and for every x ∈ R \ U(R) we have deg(x) = |U(R)|.

We point out that if {G_{i}}_{i∈I} is a family of edge-disjoint subgraphs of a graph G such that E(G) = ∪_{i∈I}E(G_{i}), then we may write G = ⊕_{i∈I}G_{i}. In this case, if G_{i} ≅ H for every i ∈ I, then we write G = ⊕_{I}H.

Theorem 3.2 ([6], Proposition 2.8). Let R be a finite commutative ring and suppose that J(R) denotes the Jacobson radical of R. Then the following statements hold:

(a) If 2 ∉ U(R), then G(R) ≅ ⊕_{J(R)^{2}}G(R/J(R)).

(b) If 2 ∈ U(R), then G(R) ≅ (⊕_{J(R)^{2}}G(R/J(R))) ⊕ (⊕_{U(R)}K_{|J(R)|}).

The next result involves the Nagata extension of a ring, and so we recall this notion here. Let R be a commutative ring and let M be a unitary R-module. We may turn the cartesian product R × M into a ring by defining the operations (r, x) + (r′, x′) := (r + r′, x + x′) and (r, x)(r′, x′) := (rr′, rx′ + r′x). This ring is called the Nagata extension of R by M and is denoted by R ⊕ M.

Theorem 3.3 ([6], Proposition 2.9). Let R be a commutative ring and let M be a finite unitary R-module. Then the following statements hold:

(a) If 2 ∉ U(R), then G(R ⊕ M) ≅ ⊕_{M^{2}}G(R).

(b) If 2 ∈ U(R), then G(R ⊕ M) ≅ (⊕_{M^{2}}G(R)) ⊕ (⊕_{U(R)}K_{|M|}).

3.3. Characterizations of certain unit graphs. A complete graph is a graph in which each pair of distinct vertices is joined by an edge. We denote the complete graph with n vertices by K_{n}. A cycle graph is a graph that consists of a single cycle.

Theorem 3.4 ([6], Theorem 3.2). Let R be a finite ring. Then the unit graph G(R) is a cycle graph if and only if R is isomorphic to one of the following rings:

(a) ℤ_{4},

(b) ℤ_{6},

(c) \{ [ \begin{matrix}a & b \\ 0 & a \end{matrix}] | a, b ∈ ℤ_{2}\}.

By applying Corollary 4.5 of [11] we obtain that G(R) is a 2-regular graph if and only if R ≅ ℤ_{2} × ⋯ × ℤ_{2} × S, where S is one of the rings appearing in the statement of Theorem 3.4.

Theorem 3.5 ([6], Theorem 3.4). Let R be a ring. Then the unit graph G(R) is a complete graph if and only if R is a division ring with Char(R) = 2, where Char(R) denotes the characteristic of R.

The following theorem characterizes the complete bipartite unit graphs of rings.

Theorem 3.6 ([6], Theorem 3.5). Let R be a commutative ring and 𝔪 be a maximal ideal of R such that |R/𝔪| = 2. Then, G(R) is a bipartite graph. Moreover, the unit graph G(R) is a complete bipartite graph if and only if R is a local ring.

In [29], the authors proved that the ring R is uniquely clean if and only if |R/𝔪| = 2 for each maximal ideal 𝔪 of R. By combining this observation with Theorem 3.6, we conclude that if, for example, R is one of the following rings, then the unit graph G(R) is bipartite.

R = ℤ_{n} for even n.

R is a uniquely clean ring.

R = S × S′, where S is a uniquely clean ring and S′ is an arbitrary ring. Also note that if n is an integer such that n = 2^{m}, then G(ℤ_{n}) is a complete

bipartite graph.

Let G_{1} and G_{2} be two graphs. The join of G_{1} and G_{2}, which is denoted by G_{1} ∨G_{2}, is a graph with vertex set V (G_{1}) ∪ V (G_{2}) and edge set E(G_{1}) ∪ E(G_{2}) ∪ {xy | x ∈ V (G_{1}), y ∈ V (G_{2})}. If we omit a perfect matching from a complete graph K_{2n}, then the resulting graph is called a cocktail party and denoted by CP(2n).

Theorem 3.7 ([6], Theorem 3.8). Let R be a ring, n be a positive integer, and let p be an odd prime. Then, G(R) ≅ K_{1} ∨ CP(p^{n} − 1) if and only if R is a field with p^{n} elements.

Note that in the above theorem, if R is a field with Char(R) ≠ 2, then the unit graph G(R) is isomorphic to K_{1} ∨ H, where H is an infinite cocktail party.

3.4. Connectedness of unit graphs. The unit graph G(ℤ_{2} × ℤ_{2}), shown in Fig. 1, is not connected. There are also many other rings which have disconnected unit graphs. For example, suppose that R = S × T where S ≅ ℤ_{2} × ℤ_{2} and T is a ring. Then G(R) is not connected. Thus unit graphs are not connected, in general.

Let R be a ring and k be a positive integer. An element r ∈ R is said to be k-good if we may write r = u_{1} + ⋯ + u_{k}, where u_{1}, …, u_{k} ∈ U(R). The ring R is said to be k-good if every element of R is k-good. Following [13], we now define an invariant of a ring, called the unit sum number, which expresses, in a fairly precise way, how the units generate the ring. The unit sum number of R, denoted by u(R), is given by:

(a) min{k | R is k−good} if R is k-good for some k ≥ 1,

(b) ω if R is not k-good for every k, but every element of R is k-good for some k (that is, when at least U(R) generates R additively),

(c) ∞ otherwise (that is, when U(R) does not generate R additively).

For example, let D be a division ring. If |D| ≥ 3, then u(D) = 2; whereas if |D| = 2, that is, D = ℤ_{2} the field of two elements, then u(ℤ_{2}) = ω. We have also u(ℤ_{2} × ℤ_{2}) = ∞ (cf. [7] for unit sum numbers of some other rings).

Theorem 3.8 ([6], Theorem 4.3). Let R be a ring. Then the unit graph G(R) is connected if and only if u(R) ≤ ω.

Note that there are infinitely many rings R such that u(R) ≤ ω and therefore, by Theorem 3.8, their unit graphs are connected.

We recall that for a graph G, a subset S of the vertex set of G is called a dominating set if every vertex not in S is adjacent to a vertex in S.

Theorem 3.9 ([6], Corollary 4.4). Let R be a ring. If U(R) is a dominating set of G(R), then the unit graph G(R) is connected.

Note that there are infinitely many rings R such that U(R) is a dominating set of G(R) and, therefore, by Theorem 3.9, the unit graph G(R) is connected. For example, if R is a 2-good ring, then U(R) is a dominating set of G(R).

Theorem 3.10 ([6], Proposition 4.6). Let R be a commutative ring. If R is reduced, then the unit graph G(R[x]) is a disconnected graph.

The following result gives us information on the connectedness of unit graphs associated with matrix rings.

Theorem 3.11 ([6], Proposition 4.7). Let R be a field with |R| > 2, and let M_{n}(R), n > 1, be the ring of n × n matrices over R. Then the unit graph G(M_{n}(R)) is a connected graph.

By applying Maschke’s theorem and the Wedderburn-Artin theorem, the above theorem implies the following result.

Theorem 3.12 ([6], Corollary 4.8). Let R be an Artinian semisimple ring, G be a finite group such that |G| is a unit in R, and let RG be the group ring. Then the unit graph G(RG) is a connected graph.

3.5. Further properties of unit graphs. A k-edge coloring of a graph G is an assignment of k labels, also called colors, to the edges of G such that every pair of distinct edges meeting at a common vertex are assigned two different colors. If G has a k-edge coloring, then G is said to be k-edge colorable. The chromatic index of G, denoted by χ′(G), is the smallest number k such that G is k-edge colorable. By Vizing’s theorem, if G is a graph whose maximum vertex degree is Δ, then Δ ≤ χ′(G) ≤ Δ + 1. Vizing’s theorem divides the graphs into two classes according to their chromatic index; graphs satisfying χ′(G) = Δ are called class 1, those with χ′(G) = Δ + 1 are class 2.

Theorem 3.13 ([6], Theorem 5.2). Let R be a finite ring. Then the unit graph G(R) is class 1.

One can easily see that, for example, diam(G(ℤ_{6})) = 3, diam(G(ℤ_{8})) = 2, and diam(G(ℤ)) = ∞. If R is a field with |R| > 2, and if M_{n}(R), n > 1, is the ring of n × n matrices over R, then diam(G(M_{n}(R))) ≤ 4.

Theorem 3.14 ([6], Corollary 5.6 and Theorem 5.7). Let R be a finite commutative ring. Then diam(G(R)) ∈ {1, 2, 3, ∞}. Moreover, the following statements hold:

(a) diam(G(R)) = 1 if and only if R is a field with Char(R) = 2.

(b) diam(G(R)) = 2 if and only if one of the following cases occurs: (1) R is a field with Char(R) ≠ 2,

(2) R is not a field and R cannot have ℤ_{2} as a quotient,

(3) R is a local ring with maximal ideal 𝔪 such that |R/𝔪| = 2 and R ≇ ℤ_{2}.

(c) diam(G(R)) = 3 if and only if R has ℤ_{2} as a quotient and cannot have ℤ_{2} ×ℤ_{2} as a quotient and R is not a local ring.

(d) diam(G(R)) = ∞ if and only if R has ℤ_{2} × ℤ_{2} as a quotient.

The finiteness of R in Theorem 3.14 is essential. For example, the unit graphs G(ℤ) and G(ℤ × ℤ) are both connected, and we have diam(G(ℤ)) = diam(G(ℤ × ℤ)) = ∞. Note that ℤ has ℤ_{2} as a quotient and cannot have ℤ_{2} × ℤ_{2} as a quotient, while ℤ × ℤ has ℤ_{2} × ℤ_{2} as a quotient.

Theorem 3.15 ([6], Proposition 5.10). Let R be a finite commutative ring. Then gr(G(R)) ∈ {3, 4, 6, ∞}.

Note that gr(G(ℤ_{5})) = 3, gr(G(ℤ_{4})) = 4, gr(G(ℤ_{6})) = 6, and gr(G(ℤ_{2})) = ∞. Therefore, for every n ∈ {3, 4, 6, ∞}, there exists a ring R such that gr(G(R)) = n. Suppose that R is a finite commutative ring, and M is a finite unitary R-module. Suppose that R ⊕ M denotes the Nagata extension of R by M. If |M| > 2, then gr(G(R ⊕ M)) ≤ 4. In particular, if 2 ∈ U(R), then gr(G(R ⊕ M)) = 3.

Unit graphs are not planar, in general. An example to illustrate this fact is the unit graph G(ℤ_{10}), which is not planar. On the other hand, there are also planar unit graphs. For example, the unit graph G(ℤ_{3} × ℤ_{3}) is a planar graph (cf. Fig. 4).

[figure: 01; 10; 12; 00; 21; 11; 22; 20; 02; G(ℤ_{3} × ℤ_{3})]

Figure 4. A planar unit graph

The following theorem gives necessary and sufficient condition for the planarity of G(R). Here, 𝔽_{4} denotes the field with four elements.

Theorem 3.16 ([6], Theorem 5.14). Let R be a finite commutative ring. Then the unit graph G(R) is planar if and only if R is isomorphic to one of the following rings:

(a) ℤ_{5},

(b) ℤ_{3} × ℤ_{3},

(c) \underbrace{ℤ_{2} × ⋯ × ℤ_{2}}_{ℓ times} ×S, where ℓ ≥ 0 and S ≅ ℤ_{2}, S ≅ ℤ_{3}, S ≅ ℤ_{4}, S ≅ 𝔽_{4}, or

S ≅ \{ [ \begin{matrix}a & b \\ 0 & a \end{matrix}] | a, b ∈ ℤ_{2}\}.

The following theorem concerns the weakly perfectness of unit graphs.

Theorem 3.17 ([22], Theorem 2.2). If R is a ring, then the unit graph G(R) is weakly perfect.

Let us note that the proof of Theorem 3.17 gives us an explicit formula for the chromatic number of G(R). For a given ring R, we may write R ≅ R_{1} × ⋯ × R_{n}, where every R_{i} is a local ring with maximal ideal 𝔪_{i}. If 2 ∉ U(R), by reordering, we may assume that R_{1}, …, R_{ℓ} all have characteristic equal to 2 with |R_{1}|/|𝔪_{1}| ≤ ⋯ ≤ |R_{ℓ}|/|𝔪_{ℓ}| and R_{ℓ+1}, …, R_{n} all have characteristic not equal to 2. Then,

χ(G(R)) = \{ \begin{matrix}\frac{1}{2^{n}} ∏_{i=1}^{n}(|R_{i}| − |𝔪_{i}|) + n & if 2 ∈ U(R), \\ |R_{1}|/|𝔪_{1}| & if 2 ∉ U(R). \end{matrix}

Note that this formula reduces to the following simpler form if all of the R_{i}s are fields.

χ(G(R)) = \{ \begin{matrix}\frac{1}{2^{n}} ∏_{i=1}^{n}(|R_{i}| − 1) + n & if 2 ∈ U(R), \\ |R_{1}| & if 2 ∉ U(R). \end{matrix}

We conclude this section with two examples which illustrate Theorem 3.17 and the above formulas. Let k > 1 be an integer and write k = p_{1}^{r_{1}} … p_{n}^{r_{n}}, where the p_{i}s are distinct prime numbers and the r_{i}s are positive integers. Therefore, we obtain ℤ_{k} ≅ ℤ_{p_{1}^{r_{1}}} × ⋯ × ℤ_{p_{n}^{rn}}, and so we have the following formula, where φ denotes the Euler phi function:

χ(G(ℤ_{k})) = \{ \begin{matrix}\frac{1}{2^{n}} φ(k) + n & if k is odd, \\ 2 & if k is even. \end{matrix}

Therefore, for example, the chromatic number of G(ℤ_{9}) is equal to four and the chromatic number of G(ℤ_{12}) is equal to two. In Fig. 5, we illustrate these points. Here the different bullets indicate the presence of the different colors.

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

Figure 5. The unit graphs G(ℤ_{9}) and G(ℤ_{12}) and their four-coloring and two-coloring

The chromatic number of G(ℤ_{3}[x]/(x^{2})) is equal to four. In Fig. 6, we illustrate this point. Here, the different bullets indicate the presence of the different colors.

[figure: 1; 1+α; 1+2α; 2α; 2; 2+2α; 2+α; 0; α]

Figure 6. The unit graph G(ℤ_{3}[x]/(x^{2})) and its four-coloring

A graph is Hamiltonian if it has a cycle, which visits every vertex exactly once; such a cycle is called a Hamiltonian cycle. In general, the problem of finding a Hamiltonian cycle in a given graph is an NP -complete problem and it is a special case of the traveling salesman problem. This is a problem in combinatorial optimization studied in operations research and theoretical computer science (cf. [12]). The only known way to determine whether a given graph has a Hamiltonian cycle is to undertake an exhaustive search. Also, till now no theorem giving a necessary and sufficient condition for a graph to be Hamiltonian is known. The study of Hamiltonian graphs has long been an important topic.

Theorem 3.18 ([23], Theorem 2.1). Let R be a ring such that R ≇ ℤ_{2} and R ≇ ℤ_{3}. Then the following statements are equivalent:

(a) The unit graph G(R) is Hamiltonian.

(b) The ring R cannot have ℤ_{2} × ℤ_{2} as a quotient.

(c) The ring R is generated by its units.

(d) The unit sum number of R is less than or equal to ω.

(e) The unit graph G(R) is connected.

4. Total graphs

In 2008, Anderson and Badawi [4] introduced the notion of total graphs of rings.

4.1. Total graphs: definition and remarks. Let R be a commutative ring and Z(R) be the set of zero divisors of R. The total graph of R, denoted by T (Γ(R)), is the graph obtained by setting all the elements of R to be the vertices and defining distinct vertices x and y to be adjacent if and only if x + y ∈ Z(R).

Three important subgraphs of total graphs are defined below. Let R be a commutative ring with Reg(R) its set of regular elements, Z(R) its set of zero divisors, and Nil(R) its ideal of nilpotent elements. Let T (Γ(R)) be the total graph of R. Then Reg(Γ(R)) is the subgraph of T (Γ(R)) with vertices Reg(R), Z(Γ(R)) is the subgraph of T (Γ(R)) with vertices Z(R), and Nil(Γ(R)) is the subgraph of T (Γ(R)) with vertices Nil(R).

4.2. Basic properties of total graphs. The study of T (Γ(R)) breaks naturally into two cases depending on whether or not Z(R) is an ideal of R. In the following, we provide general structure theorems for Reg(Γ(R)), Z(Γ(R)), and Nil(Γ(R)) in the case where Z(R) is an ideal of R.

Theorem 4.1 ([4], Theorem 2.2). Let R be a commutative ring such that Z(R) is an ideal of R, and let |Z(R)| = α and |R/Z(R)| = β.

(1) If 2 ∈ Z(R), then Reg(Γ(R)) is the union of β − 1 disjoint K_{α}s.

(2) If 2 ∉ Z(R), then Reg(Γ(R)) is the union of (β − 1)/2 disjoint K_{α,α}s.

Theorem 4.2 ([4], Theorem 2.1). Let R be a commutative ring such that Z(R) is an ideal of R. Then Z(Γ(R)) is a complete (induced) subgraph of T (Γ(R)) and Z(Γ(R)) is disjoint from Reg(Γ(R)).

Theorem 4.3 ([4], Theorem 2.10). Let R be a commutative ring:

(1) Nil(Γ(R)) is a complete (induced) subgraph of Z(Γ(R)).

(2) Each vertex of Nil(Γ(R)) is adjacent to each distinct vertex.

(3) Nil(Γ(R)) is disjoint from Reg(Γ(R)).

(4) If {0} ≠ Nil(R) ⊆ Z(R), then gr(Z(Γ(R))) = 3.

4.3. Further properties of total graphs. In [4], the authors have computed the diameter and the girth of Reg(Γ(R)), and show that Z(Γ(R)) is always connected and T (Γ(R)) is never connected if Z(R) is an ideal. Also, when Z(R) is not an ideal of R, they have shown that Z(Γ(R)) is always connected but never complete, Z(Γ(R)) and Reg(Γ(R)) are never disjoint subgraphs of T (Γ(R)) and |Z(R)| > 3.

In the following, further properties of T (Γ(R)) are given.

Theorem 4.4 ([25], Lemma 1.1). Let R be a commutative ring. Let x be a vertex of T (Γ(R)). Then the degree of x is either |Z(R)| or |Z(R)| − 1. In particular, if 2 ∈ Z(R), then T (Γ(R)) is a (|Z(R)| − 1)-regular graph.

Let S_{k} denote the sphere with k handles, where k is a nonnegative integer, that is, S_{k} is an oriented surface of genus k. The genus of a graph G, denoted by γ(G), is the minimum integer n such that the graph can be embedded in S_{n}. Therefore, a graph G is planar if and only γ(G) = 0. A graph is called toroidal if γ(G) = 1. Note that if H is a subgraph of a graph G, then γ(H) ≤ γ(G).

Theorem 4.5 ([25], Lemma 1.3). Let 𝔽_{q} denote the field with q elements. Then the total graph of 𝔽_{2} ×𝔽_{q} is isomorphic to K_{2} ×K_{q}. Furthermore, for any positive integer m and q > 2,

γ(T (Γ(𝔽_{2^{m}} × 𝔽_{q}))) ≥ 2^{m} ⌈\frac{(q − 3)(q − 4)}{12}⌉ .

Theorem 4.6 ([25], Theorem 1.4). For any positive integer g, there are finitely many finite rings R whose total graph has genus g.

Theorem 4.7 ([25], Theorem 1.5). Let R be a finite commutative ring such that T (Γ(R)) is planar. Then the following hold:

(a) If R is a local ring, then R is a field or R is isomorphic to the one of the 9 following rings: ℤ_{4}, ℤ_{2}[x]/(x^{2}), ℤ_{2}[x]/(x^{3}), ℤ_{2}[x, y]/(x, y)^{2}, ℤ_{4}[x]/(2x, x^{2}), ℤ_{4}[x]/(2x, x^{2} − 2), ℤ_{8}, 𝔽_{4}[x]/(x^{2}), ℤ_{4}[x]/(x^{2} + x + 1).

(b) If R is not a local ring, then R is an infinite integral domain or R is isomorphic to ℤ_{2} × ℤ_{2} or ℤ_{6}.

Theorem 4.8 ([25], Theorem 1.6). Let R be a finite commutative ring such that T (Γ(R)) is toroidal. Then the following statements hold:

(a) If R is a local ring, then R is isomorphic to ℤ_{9} or ℤ_{3}[x]/(x^{2}).

(b) If R is not a local ring, then R is isomorphic to one of the following rings: ℤ_{2} × 𝔽_{4}, ℤ_{3} × ℤ_{3}, ℤ_{2} × ℤ_{4}, ℤ_{2} × ℤ_{2}[x]/(x^{2}), ℤ_{2} × ℤ_{2} × ℤ_{2}.

[figure: 00; 13; 10; 12; 10; 11; 02; 11; 01; 03; 01; 00; 13; Embedding of ℤ_{2} × ℤ_{4}; 00; 1α^{2}; 10; 1α; 10; 11; 0α; 11; 01; 0α^{2}; 01; 00; 1α^{2}; Embedding of ℤ_{2} × 𝔽_{4}]

[figure: 11; 12; 22; 22; 21; 01; 10; 21; 02; 00; 20; 11; 12; Embedding of ℤ_{3} × ℤ_{3}; 10; 11; 1α; 1α^{2}; 20; 21; 2α; 2α^{2}; 01; 0α; 0α^{2}; 00; A subgraph of T (Γ(ℤ_{3} × 𝔽_{4})); that is a subdivision of K_{5,4}]

Figure 7. Embeddings in the torus and a subgraph of T (Γ(ℤ_{3} × 𝔽_{4}))

5. Graphs similar to known graphs

Let R be a ring and U(R) be the set of unit elements of R. The counit graph of R, denoted by G̃(R), is the graph obtained by setting all the elements of R to be the vertices and defining distinct vertices x and y to be adjacent if and only if x − y ∈ U(R). This graph was defined in a paper of Lucchini and Maróti [19]. It is very similar to the unit graph. For this graph, one can deduce similar properties such as those of unit graphs. In some cases, dealing with this graph is better than with the unit ones.

In this direction, we may define a graph similar to the total graph. In the following, we define this graph, and then we give an application of it to the rings.

Definition 5.1. Let R be a ring and Z(R) be the set of zero divisors of R. The cototal graph of R, denoted by T̃(Γ(R)), is the graph obtained by setting all the elements of R to be the vertices and defining distinct vertices x and y to be adjacent if and only if x − y ∈ Z(R).

By using cototal graphs, we characterize the rings which are additively generated by their zero divisors.

Theorem 5.2. Let R be a finite ring. Then the following statements are equivalent: (a) The ring R is generated by its zero divisors.

(b) The cototal graph T̃(Γ(R)) is connected.

(c) The cototal graph T̃(Γ(R)) is Hamiltonian.

For the proof of Theorem 5.2, we need the following well-known fact. We state and prove it here for the convenience of the reader.

Lemma 5.3. Let x and y be distinct vertices of a graph G. If there is a walk between x and y, then there is also a path between x and y.

Proof. By assumption, there is a walk between x and y, and so we may select a walk

W : x = v_{0} ⟶^{e_{1}} v_{1} ⟶ ⋯ ⟶^{e_{k}} v_{k} = y

of minimal length k between x and y. If W is not a path, select a vertex that appears twice, say v_{i} = v_{j} where i < j. Consider

W′ : x = v_{0} ⟶^{e_{1}} v_{1} ⟶ ⋯ ⟶^{e_{i}} v_{i} ⟶^{e_{j+1}} v_{j+1} ⟶ ⋯ ⟶^{e_{k}} v_{k} = y.

Then W′ is a walk between x and y with length shorter than k, a contradiction. Therefore, W is a path between x and y. □

Proof of Theorem 5.2. (a)⇒(b): Suppose that a ∈ R. Since R is generated by its zero divisors, we may write a = c_{1} + ⋯ + c_{n}, where c_{i} ∈ Z(R), 1 ≤ i ≤ n. We now have the walk

0 ⟶^{e_{1}} c_{1} ⟶^{e_{2}} c_{1} + c_{2} ⟶ ⋯ ⟶^{e_{n}} c_{1} + ⋯ + c_{n} = a

between 0 and a.

This implies that for every x, y ∈ R, there is a walk W_{1} between x and 0, as well as a walk W_{2} between 0 and y. The walks W_{1} and W_{2} together form a walk W between x and y. By using Lemma 5.3, we conclude that there is also a path P between x and y, which implies the connectedness of T̃(Γ(R)).

(b)⇒(a): Suppose that a ∈ R can be written as a sum of zero divisors and b ∈ R is adjacent to a in T̃(Γ(R)). Therefore a − b ∈ Z(R), and so we may write b = a − c, for some c ∈ Z(R). Thus, b is a sum of zero divisors.

Now suppose that x ∈ R is given. Since T̃(Γ(R)) is connected, there exists a path between x and 0 and, therefore, by the above observation, we conclude that x is a sum of zero divisors. This means that R is generated by its zero divisors. □

Let G_{1} and G_{2} be two graphs. An isomorphism from G_{1} to G_{2} is a bijection f : V (G_{1}) ⟶ V (G_{2}) such that {x, y} ∈ E(G_{1}) if and only if {f(x), f(y)} ∈ E(G_{2}). An automorphism of a graph G is an isomorphism from G to G. The set of all automorphisms of the graph G forms a group, denoted by Aut(G), called the automorphism group of G. A subgroup A of Aut(G) is called transitive if for every x, y ∈ V (G), there is f ∈ Aut(G) such that y = f(x). In the following, we state a significant result by Lovász [17] regarding these notions.

Lemma 5.4 ([17], Page 89, Exercise 17). Let G be a connected graph such that Aut(G) contains a commutative transitive subgroup. Then G is a Hamiltonian graph.

Proof of Theorem 5.2. (b)⇒(c): Suppose that a ∈ R and define f_{a} : R ⟶ R by f_{a}(x) = x + a. It is obvious that f_{a} is a bijection and {x, y} ∈ E(T̃(Γ(R))) if and only {f_{a}(x), f_{a}(y)} ∈ E(T̃(Γ(R))). Therefore, f_{a} ∈ Aut(T̃(Γ(R))). Now, it is easy to see that {f_{a} | a ∈ R} is a commutative transitive subgroup of Aut(T̃(Γ(R))). Therefore by Lemma 5.4, we conclude that T̃(Γ(R)) is Hamiltonian.

(c)⇒(b): It is obvious by definition. □

6. A brief glance at the graphs attached to other algebraic structures

In the last decade, many authors have studied zero-divisor graphs of rings or other graphs associated with other algebraic structures. For instance, Nimbhorkar et al. [30] have shown that Beck’s conjecture holds true for commutative semigroups with zero in which each element is idempotent. These semigroups are called meet-semilattices. Also, there are many graphs, which are attached to the groups. Perhaps the best known one is the Cayley graph of a group. For other ones, we may point to the prime graph and the commutating graph of a finite group, and graphs associated with character degrees as well as conjugacy class sizes in finite groups. For a survey and recent results concerning the two last ones, we refer the reader to [16]. Recently, Halaš, and Jukl [15] introduced the zero-divisor graphs of posets and answered Beck’s conjecture affirmatively in this case. More recently, a different method of associating a zero-divisor graph to a poset P was proposed by Lu and Wu in [18]. The graph defined by them is slightly different from the one defined in [15] and [35], where the vertex set of the graph consists of all the elements of P. The vertex set of the graph defined in [18] consists of all nonzero zero divisors of P. The study of the zero-divisor graphs of posets was then continued by Xue and Liu in [35]. Let us we give a short review of zero-divisor graphs of posets.

Let P be a nonempty set. A binary relation ≤ on P is called a partial order on P if ≤ is reflexive, antisymmetric, and transitive. A set that is equipped with a partial order is called a partially ordered set (for short: poset). Let P be a poset and let Q be nonempty subset of P. If there exists y ∈ Q such that y ≤ x for every x ∈ Q, then y is called the minimum element of Q. Now, let P be a poset with a minimum element 0. We denote P \ {0} by P^{×}. For every x, y ∈ P, denote L(x, y) = {z ∈ P | z ≤ x and z ≤ y}. An element x ∈ P is called a zero divisor of P if there exists y ∈ P^{×} such that L(x, y) = {0}. We denote the set of zero divisors of P by Z(P) and we consider Z(P)^{×} := Z(P) \ {0}. The zero-divisor graph of P, denoted by Γ(P), is the graph obtained by setting all the elements of Z(P)^{×} to be the vertices and defining distinct vertices x and y to be adjacent if and only if L(x, y) = {0}.

In [10], Chakrabarty et al. have considered the intersection graph G(R) of nontrivial left ideals of a ring R, that is, a graph whose vertices are in a one-to-one correspondence with all nontrivial left ideals of R and two distinct vertices are joined by an edge if and only if the corresponding left ideals of R have a nontrivial intersection. They have characterized the rings R for which the graph G(R) is connected and have obtained several necessary and sufficient conditions on the ring R such that G(R) is complete. For a commutative ring R with identity, they showed that G(R) is complete if and only if G(R[x]) is also complete. In particular, they determined the values of n for which G(ℤ_{n}) is connected, complete, bipartite, planar or has a cycle. They also characterized the finite graphs which arise as the intersection graphs of ℤ_{n} and determined the set of all nonisomorphic graphs of ℤ_{n} for a given number of vertices. Finally, they determined the values of n for which the graph of ℤ_{n} is Eulerian and Hamiltonian.

Acknowledgments

Part of this work was done while the second author visited the Delhi Center of the Indian Statistical Institute (ISID). He would like to thank the Academy of Sciences for the Developing World (TWAS) and ISID for sponsoring his visits to New Delhi in July–August 2007 and January 2010. Especially, he would like to express his thanks to Professor Rajendra Bhatia for the hospitality enjoyed at ISID.

References

[1] D. D. Anderson, V. P. Camillo, Commutative rings whose elements are a sum of a unit and idempotent, Comm. Algebra 30 (2002), no. 7, 3327–3336.

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

[3] D. F. Anderson, M. Axtell, J. Stickles, Zero-divisor graphs in commutative rings, Commutative Algebra, Noetherian and non-Noetherian Perspectives, 23-45, Springer-Verlag, New York, 2010.

[4] D. F. Anderson, A. Badawi, The total graph of a commutative ring, J. Algebra 320 (2008), no. 7, 2706–2719.

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

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

[7] N. Ashrafi, P. Vámos, On the unit sum number of some rings, Q. J. Math. 56 (2005), no. 1, 1–12.

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

[9] G. D. Birkhoff, A determinant formula for the number of ways of coloring a map, Ann. of Math. (2) 14 (1912/13), no. 1-4, 42–46.

[10] I. Chakrabarty, S. Ghosh, T. K. Mukherjee, M. K. Sen, Intersection graphs of ideals of rings, Discrete Math. 309 (2009), no. 17, 5381–5392,

[11] D. Dolžan, Group of units in a finite ring, J. Pure Appl. Algebra 170 (2002), no. 2-3, 175–183.

[12] M. R. Garey, D. S. Johnson, Computers and Intractabilitiy: A Guide to the Theory of NP-Completeness, W. H. Freman and Company, New York, 1979.

[13] B. Goldsmith, S. Pabst, A. Scott, Unit sum numbers of rings and modules, Quart. J. Math. Oxford Ser. (2) 49 (1998), no. 195, 331–344.

[14] 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.

[15] R. Halaš, M. Jukl, On Beck’s coloring of posets, Discrete Math. 309 (2009), no. 13, 4584–4589.

[16] M. L. Lewis, An overview of graphs associated with character degrees and conjugacy class sizes in finite groups, Rocky Mountain J. Math. 38 (2008), no. 1, 175–211.

[17] L. Lovász, Combinatorial Problems and Exercises, Corrected reprint of the 1993, Second Edition, AMS Chelsea Publishing, Providence, RI, 2007.

[18] D. Lu, T. Wu, The zero-divisor graphs of posets and an application to semigroups, Graphs Combin. 26 (2010), no. 6, 793–804.

[19] A. Lucchini, A. Maróti, Some results and questions related to the generating graph of a finite group, Proceedings of the Ischia Group Theory Conference, 2008, to appear.

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

[21] 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.

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

[23] 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.

[24] H. R. Maimani, M. Salimi, A. Sattari, S. Yassemi, Comaximal graph of commutative rings, J. Algebra 319 (2008), no. 4, 1801–1808.

[25] H. R. Maimani, C. Wickham, S. Yassemi, Rings whose total graphs have genus at most one, Rocky Mountain J. Math., to appear.

[26] C. McDiarmid, B. Reed, Channel assignment and weighted colouring, Networks 36 (2000), 114–117.

[27] S. M. Moconja, Z. Z. Petrović, On the structure of comaximal graphs of commutative rings with identity, Bull. Aust. Math. Soc. 83 (2011), no. 1, 11–21.

[28] W. K. Nicholson, Lifting idempotents and exchange rings, Trans. Amer. Math. Soc. 229 (1977), 269–278.

[29] W. K. Nicholson, Y. Zhou, Rings in which elements are uniquely the sum of an idempotent and a unit, Glasg. Math. J. 46 (2004), no. 2, 227–236.

[30] S. K. Nimbhokar, M. P. Wasadikar, L. DeMeyer, Coloring of meet-semilattices, Ars Combin. 84 (2007), 97–104.

[31] Z. Z. Petrović, S. M. Moconja, On graphs associated to rings, Novi Sad J. Math. 38 (2008), no. 3, 33–38.

[32] P. K. Sharma, S. M. Bhatwadekar, A note on graphical representation of rings, J. Algebra 176 (1995), no. 1, 124–127.

[33] H. J. Wang, Graphs associated to co-maximal ideals of commutative rings, J. Algebra 320 (2008), no. 7, 2917–2933.

[34] H. J. Wang, Co-maximal graph of non-commutative rings, Linear Algebra Appl. 430 (2009), no. 2-3, 633–641.

[35] Z. Xue, S. Liu, Zero-divisor graphs of partially ordered sets, Appl. Math. Lett. 23 (2010), no. 4, 449–452.

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.

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

A. Tehranian, Science and Research Branch, Islamic Azad University (IAU), Tehran, Iran.

  E-mail address: tehranian1340@yahoo.com

S. Yassemi, School of Mathematics, Statistics and Computer Science, College of Science, University of Tehran, Tehran, Iran.

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