UNIT GRAPHS ASSOCIATED WITH RINGS

N. ASHRAFI, H. R. MAIMANI, M. R. POURNAKI, AND S. YASSEMI

Abstract. Let R be a ring with nonzero identity. The unit graph of R, denoted by G(R), has its set of vertices equal to the set of all elements of R; distinct vertices x and y are adjacent if and only if x+y is a unit of R. In this article, the basic properties of G(R) are investigated and some characterization results regarding connectedness, chromatic index, diameter, girth, and planarity of G(R) are given. (These terms are defined in Definitions and Remarks 4.1, 5.1, 5.3, 5.9, and 5.13.)

1. Introduction

Let n be a positive integer, and let ℤ_{n} be the ring of integers modulo n. Ralph P. Grimaldi defined a graph G(ℤ_{n}) based on the elements and units of ℤ_{n} (cf. [7]). 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}. That is, xy is an edge if and only if x + y is a unit. For a positive integer m, it follows that G(ℤ_{2m}) is a φ(2m)-regular graph, where φ is the Euler phi function (cf. Definitions 2.3). 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 (cf. Definitions and Remarks 3.1). The odd case is not quite so easy, but the structure is clear and the results are similar to the even case. 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 (cf. Definitions and Remarks 2.6). This leads to an explicit formula for the chromatic polynomial p(k) of G(ℤ_{p}). Here, p(k) is the number of ways needed to color the vertices of G(ℤ_{p}) using at most k 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 in order to study the 4-color problem (cf. [2]). The article [7] also concludes with some properties of the graphs G(ℤ_{p^{m}}), where p is a prime number and m ≥ 2.

We now 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 [12]. The definition of G(R) and its basic properties are given in the next section. In Section 3, we give some characterizations of unit graphs. In Section 4, we give a necessary and sufficient condition for G(R) to be connected; connectedness is related to the unit sum number (cf. Definitions and Remarks 4.2). We define and study chromatic index, diameter, girth, and the planarity of G(R) in Section 5.

2000 Mathematics Subject Classification. Primary: 05C75; Secondary: 13A10, 13A15.

Key words and phrases. Unit graph, Connectedness, Chromatic index, Diameter, Girth, Planarity.

The research of N. Ashrafi was in part supported by a grant from Semnan University. The research of H. R. Maimani and M. R. Pournaki was in part supported by a grant from IPM (No. 87050213 and No. 87200111). The research of S. Yassemi was in part supported by a grant from the University of Tehran (No. 6103023/1/07).

In what follows, all rings are associative with nonzero identity, denoted by 1, which is preserved by ring homomorphisms and inherited by subrings. Also throughout the article, by a graph G we mean a finite undirected graph without loops or multiple edges (unless otherwise specified). We use the notation of Kaplansky [9] and Chartrand and Oellermann [3].

2. Basic notation and properties

In this section we study the basic properties of unit graphs. First we define the unit graph and the closed unit graph corresponding to an associative ring.

Definitions and Remarks 2.1. Let R be a ring and U(R) be the set of unit elements of R. The unit graph of R, denoted 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” in the definition, we obtain the closed unit graph denoted \overline{G}(R); this graph may have loops. Note that if 2 ∉ U(R), then \overline{G}(R) = G(R).

The graphs in Fig. 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}); 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.

Next we give additional basic notation and define graph products.

Definitions and Remarks 2.2. For a graph G, let V (G) denote the set of vertices, and let E(G) denote the set of edges. Let G_{1} and G_{2} be two vertex-disjoint graphs. The category product of G_{1} and G_{2} is denoted 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, for given rings R_{1} and R_{2}, two distinct vertices (x, y), (x′, y′) ∈ V (\overline{G}(R_{1}) ˙×\overline{G}(R_{2})) are adjacent if and only if x is adjacent to x′ in \overline{G}(R_{1}) and y is adjacent to y′ in \overline{G}(R_{2}). This implies that \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.

We now state some basic properties of unit graphs. First we give more definitions.

Definitions 2.3. For a graph G and vertex x ∈ V (G), the degree of x, denoted deg(x), is the number of edges of G incident with x. For every nonnegative integer r, the graph G is called r-regular if the degree of each vertex of G is equal to r. Also, for a given vertex x ∈ V (G), the neighbor set of x is the set N_{G}(x) := {v ∈ V (G) | v is adjacent to x}. Moreover, if G has a loop at vertex x, then we always assume that x ∈ N_{G}(x). The closed neighbor set of x, is the set N_{G}[x] := N_{G}(x) ∪ {x}.

Proposition 2.4 shows that, if 2 is not a unit element in the ring R, then the unit graph of R is a |U(R)|-regular graph (cf. Definitions 2.3). The unit graph is not |U(R)|-regular when 2 is a unit of R.

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)|.

Proof. For the proof of both (a) and (b), suppose that the vertex x ∈ R is given. We have R + x = R, and so for every u ∈ U(R) there exists an element x_{u} ∈ R such that x_{u} + x = u. Clearly, x_{u} is uniquely determined by u.

First, suppose that 2 ∉ U(R). In this case x_{u} ≠ x and so x_{u} is adjacent to x in G(R). Therefore, f : U(R) ⟶ N_{G(R)}(x) given by f(u) = x_{u} is a well-defined function. It is easy to see that f is a bijection, and therefore, deg(x) = |N_{G(R)}(x)| = |U(R)|. This shows that, in this case, the unit graph G(R) is a |U(R)|-regular graph. This completes the proof of (a).

Second, suppose that 2 ∈ U(R) and x ∈ R \ U(R). In this case, we have again x_{u} ≠ x, and so x_{u} is adjacent to x in G(R). Therefore, the above observation is still valid, which shows that deg(x) = |U(R)|.

Finally, suppose that 2 ∈ U(R) and x ∈ U(R). In this case, 2x ∈ U(R) and we have x_{u} ≠ x for u ≠ 2x and x_{2x} = x. Now x_{u} is adjacent to x in G(R) for u ≠ 2x. Therefore, f : U(R) ⟶ N_{G(R)}[x] given by f(u) = x_{u} is a well-defined function. It is easy to see that f is a bijection and, therefore, deg(x) = |N_{G(R)}(x)| = |N_{G(R)}[x]|−1 = |U(R)|−1. Thus (b) holds. □

Remark 2.5. Let R be a finite local ring and let 𝔪 be a maximal ideal of R. If |R/𝔪| > 2, then |U(R)| ≥ 2|R|/3. Thus for every x, y ∈ R, by using the proof of Proposition 2.4, we may write

\begin{aligned}|N_{\overline{G}(R)}(x) ∩ N_{\overline{G}(R)}(y)| & = |N_{\overline{G}(R)}(x)| + |N_{\overline{G}(R)}(y)| − |N_{\overline{G}(R)}(x) ∪ N_{\overline{G}(R)}(y)| \\ & ≥ |U(R)| + |U(R)| − |R| ≥ |R|/3 > 0. \end{aligned}

This implies that N_{\overline{G}(R)}(x) ∩ N_{\overline{G}(R)}(y) ≠ ∅. We will use this result in the proof of Lemma 5.5.

Definitions and Remarks 2.6. 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}. For r a nonnegative integer, an r-partite 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 2-partite graph (also called the complete bipartite graph) with exactly two partitions of size m and n, is denoted by K_{m,n}. A clique of a graph G is a complete subgraph of G. A coclique in a graph G is a set of pairwise nonadjacent vertices. A subgraph H of a graph G is called a spanning subgraph if V (H) = V (G). A 1-regular spanning subgraph H of G is called a perfect matching of G. For a graph G and a nonempty subset S ⊆ V (G), the vertex-induced subgraph, denoted ⟨S⟩, is the subgraph of G with vertex-set S and edges incident to members of S. Note that subgraphs may be induced by sets of edges. Indeed, for a graph G and a nonempty subset A ⊆ E(G), the edge-induced subgraph, denoted ⟨A⟩, is the subgraph of G with edge-set A and vertex-set consists of all ends of edges of A. We also 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.

We need the following lemma to prove Proposition 2.8.

Lemma 2.7. Let R be a commutative ring and suppose that J(R) denotes the Jacobson radical of R. If x, y ∈ R, then the following statements hold:

(a) If x + J(R) and y + J(R) are adjacent in G(R/J(R)), then every element of x + J(R) is adjacent to every element of y + J(R) in G(R);

(b) If 2x ∉ U(R), then x + J(R) is a coclique in G(R);

(c) If 2x ∈ U(R), then x + J(R) is a clique in G(R).

Proof. For part (a), suppose that a ∈ x + J(R) and b ∈ y + J(R) are given. We may write a = x + j and b = y + j′, where j, j′ ∈ J(R). Since x + J(R) and y + J(R) are adjacent in G(R/J(R)), there exists a unit element u ∈ U(R) in such a way that (x+J(R))+(y+J(R)) = u+J(R). Thus x+y−u = (a+b)−(j +j′)−u ∈ J(R). Now suppose, on the contrary, that a + b is not a unit element in R. Therefore, ⟨a + b⟩ is a proper ideal of R, and so there exists a maximal ideal 𝔪 of R such that ⟨a + b⟩ ⊆ 𝔪. Thus a + b ∈ 𝔪. On the other hand, j + j′ and (a + b) − (j + j′) − u are elements of 𝔪 and so u ∈ 𝔪, a contradiction. Thus a + b ∈ U(R), and therefore, a and b are adjacent in G(R).

For part (b), suppose that two elements of x + J(R), say z and z′, are adjacent in G(R). Therefore, z + z′ ∈ U(R). We may write z = x + j and z′ = x + j′, where j, j′ ∈ J(R). Thus 2x + j + j′ ∈ U(R). By the assumption, 2x ∉ U(R), and so there exists a maximal ideal 𝔪 of R such that ⟨2x⟩ ⊆ 𝔪. Therefore, 2x ∈ 𝔪 and since j + j′ ∈ 𝔪, we obtain that 2x + j + j′ ∈ 𝔪. Therefore, 𝔪 has a unit element, a contradiction. This means that x + J(R) is a coclique in G(R).

For part (c), suppose that z and z′ are arbitrary elements of x+J(R). We may write z = x + j and z′ = x + j′, where j, j′ ∈ J(R). If z + z′ is not a unit element of R, then there exists a maximal ideal 𝔪 of R such that ⟨z+z′⟩ ⊆ 𝔪. Thus z+z′ = 2x+j+j′ ∈ 𝔪 and since j + j′ ∈ 𝔪, we obtain that 2x ∈ 𝔪, a contradiction with the assumption that 2x ∈ U(R). Thus z + z′ ∈ U(R) and so z and z′ are adjacent in G(R). This means that x + J(R) is a clique in G(R). □

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)|}).

Proof. Clearly, we may partition R into subsets x_{i} + J(R), i ∈ I, where {x_{i}}_{i∈I} is a set of representatives of the distinct cosets of J(R) in R/J(R). Also, by part (a) of Lemma 2.7, for every i, j ∈ I, if x_{i} + J(R) and x_{j} + J(R) are adjacent in G(R/J(R)), then every element of x_{i} + J(R) is adjacent to every element of x_{j} + J(R) in G(R).

Now, for part (a), the assumption 2 ∉ U(R) implies that for every i ∈ I, 2x_{i} ∉ U(R) and so, by part (b) of Lemma 2.7, x_{i} + J(R) is a coclique in G(R). Therefore, G(R) ≅ ⊕_{J(R)^{2}}G(R/J(R)).

For part (b), the assumption 2 ∈ U(R) implies that 2x_{i} ∈ U(R), for every i ∈ I with x_{i} ∈ U(R). Therefore, by part (c) of Lemma 2.7, x_{i} + J(R) is a clique in G(R), for every i ∈ I with x_{i} ∈ U(R). Thus comparing with part (a), we conclude that G(R) ≅ (⊕_{J(R)^{2}}G(R/J(R))) ⊕ (⊕_{U(R)}K_{|J(R)|}). □

Our 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. Clearly (1, 0) is the identity of R⊕M.

The following result gives information about the unit graph of the Nagata extension of a ring.

Proposition 2.9. Let R be a commutative ring and let M be a finite unitary Rmodule. 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|}).

Proof. First, for every r ∈ R, we define W_{r} = {(r, x) | x ∈ M}. Clearly, for distinct elements r and r′ of R, W_{r} ∩ W_{r′} = ∅, and we have R ⊕ M = ∪_{r∈R}W_{r}. Therefore, we may partition R ⊕ M into subsets W_{r}, r ∈ R. One easily verifies that (r, x) ∈ R ⊕ M is a unit if and only if r ∈ R is a unit. Therefore, if (r, x) ∈ W_{r} is adjacent to (r′, x′) ∈ W_{r′} in G(R ⊕ M), then r is adjacent to r′ in G(R). In addition, if r is adjacent to r′ in G(R), then every element of W_{r} is adjacent to every element of W_{r′} in G(R⊕M). Thus for every e ∈ E(G(R)), the unit graph G(R⊕M) has a subgraph, say H^{e}, which is isomorphic to K_{|M|,|M|}. On the other hand, by [3, Page 192], we have K_{|M|,|M|} = ⊕_{i∈M}M_{i}^{(e)}, where each of M_{i}^{(e)} is a perfect matching of K_{|M|,|M|}. We consider K_{i} := ⊕_{e∈E(G(R))}M_{i}^{(e)}, i ∈ M, which is a subgraph of G(R ⊕ M).

Now, for part (a), the assumption 2 ∉ U(R) implies that for every r ∈ R, W_{r} is a coclique in G(R ⊕ M). Therefore, we may write G(R ⊕ M) ≅ ⊕_{i∈M}K_{i}. If for e ∈ E(G(R)) we choose x_{i}^{(e)} ∈ E(M_{i}^{(e)}), then the edge-induced subgraph ⟨x_{i}^{(e)}⟩ of G(R) is isomorphic to G(R). Since every perfect matching M_{i}^{(e)} contains |M| edges, we obtain that K_{i} ≅ ⊕_{i∈M}G(R) and so we have G(R ⊕ M) ≅ ⊕_{x∈M}(⊕_{i∈M}G(R)) ≅ ⊕_{M^{2}}G(R).

Finally, for part (b), it is easy to see that the assumption 2 ∈ U(R) implies that for every r ∈ U(R), W_{r} is a clique in G(R ⊕ M), and so comparing with part (a), we conclude that G(R ⊕ M) ≅ (⊕_{M^{2}}G(R)) ⊕ (⊕_{U(R)}K_{|M|}). □

3. Characterizations of certain unit graphs

In this section, we study more properties and consequences of the unit graphs.

Definitions and Remarks 3.1. 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 cycle of a graph is a path such that the start and end vertices are the same. Two cycles are considered the same if they consist of the same vertices and edges. The number of edges (counting repeats) in a walk, path or a cycle, is called its length. A cycle graph is a graph that consists of a single cycle. We denote the cycle graph with n vertices by C_{n}. If a graph G is not bipartite then G contains a cycle of odd length. This result was found by the Hungarian mathematician, Dénes König (1884–1944), in 1916 (cf. [10]). His celebrated textbook Theorie der endlichen und unendlichen Graphen appeared in 1936, and was the first book to present graph theory as a subject in its own right (cf. [11]). Note that the converse of König’s result is also true, and so the bipartite graphs are characterized by the absence of cycles of odd length.

The following result characterizes the unit graphs of rings that are cycle graphs.

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}\}.

Proof. Suppose that the unit graph G(R) is a cycle graph. By applying Corollary 4.5 of [5] we obtain that R is isomorphic to one of the following rings:

R_{1} = ℤ_{3}; R_{2} = ℤ_{4};

R_{3} = \{ [ \begin{matrix}a & b \\ 0 & a \end{matrix}] | a, b ∈ ℤ_{2}\};

R_{4} = \{ [ \begin{matrix}a & b \\ 0 & c \end{matrix}] | a, b, c ∈ ℤ_{2}\};

S_{i} = ℤ_{2} × R_{i}, 1 ≤ i ≤ 4. Among these rings only the unit graphs of R_{2}, R_{3}, and S_{1} are cycle graphs: G(R_{2}) ≅

C_{4} ≅ G(R_{3}) and G(S_{1}) ≅ C_{6}. This completes the proof of the theorem. □

Remark 3.3. By applying Corollary 4.5 of [5] 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 appeared in the statement of Theorem 3.2.

The following result characterizes the unit graphs of rings that are complete graphs (cf. Definitions and Remarks 2.6). Here the characteristic of the ring R is denoted by Char(R).

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.

Proof. Suppose that the unit graph G(R) is a complete graph. Let r ≠ 0 be given in R. Since the zero of R is adjacent to r, we have r = r + 0 ∈ U(R). Therefore, every nonzero element of R is a unit and so R is a division ring. On the other hand, 1 is not adjacent to −1, and so we have 1 = −1 which implies that Char(R) = 2.

Conversely, if R is a division ring with Char(R) = 2, then each pair of distinct elements of R is adjacent, and so the unit graph G(R) is a complete graph. □

We now state Theorem 3.5, which characterizes the complete bipartite unit graphs of rings (cf. Definitions and Remarks 2.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.

Proof. Let V_{1} = 𝔪 and V_{2} = R \ 𝔪. We have V (G(R)) = V_{1} ∪ V_{2} and V_{1} ∩ V_{2} = ∅. Therefore V_{1} and V_{2} partition V (G(R)) into two subsets. It is clear that no pair of distinct elements of V_{1} are adjacent. Thus to prove the first part it is enough to show that no elements of V_{2} are adjacent. In order to do this, fix an element in R \ 𝔪, say a. By assumption, we have R = 𝔪 ∪ (𝔪 + a) = 𝔪 ∪ (𝔪 + (−a)). Now for distinct elements x and y in R \ 𝔪, we may write x = m + a and y = m′ − a where m, m′ ∈ 𝔪. If x + y ∈ U(R), then we conclude that m + m′ ∈ U(R). Therefore, 𝔪 has a unit element and hence 𝔪 = R, a contradiction. Thus x + y ∉ U(R), which implies that x and y are not adjacent. Therefore no elements of V_{2} are adjacent. Hence G(R) is a bipartite graph.

Moreover, suppose that R is a local ring with 𝔪 as the unique maximal ideal. Let x ∈ V_{1} and y ∈ V_{2} be given. If x + y ∉ U(R), then x + y ∈ V_{1} and so y ∈ V_{1}, a contradiction. Thus x+y ∈ U(R), which implies that x and y are adjacent. Therefore, each vertex of V_{1} is joined to every vertex of V_{2}, and so G(R) is complete bipartite.

Finally, we suppose that the unit graph G(R) is a complete bipartite graph. Let V_{1} and V_{2} be two parts of G(R), and suppose that 0 ∈ V_{1}. This easily implies that V_{2} = U(R). We claim that V_{1} = J(R), the Jacobson radical of R. Clearly, J(R) ⊆ V_{1}. Now suppose that x ∈ V_{1} is given. Then x is not a unit, and so for every a ∈ R, −ax is not a unit; that is, −ax ∈ V_{1}. Thus 1 − ax ∈ U(R), for every a ∈ R. This implies that x ∈ J(R), and therefore V_{1} ⊆ J(R). Hence we have V_{1} = J(R) = R \ U(R), which implies that R is a local ring. □

Remarks 3.6. 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. This definition dates back to 1977 where it was introduced by Nicholson [14]. In [15] the authors proved that the ring R is uniquely clean if and only if for each maximal ideal 𝔪 of R, |R/𝔪| = 2. By combining this observation with Theorem 3.5, 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.

Definitions 3.7. 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})}. We recall that if we omit a perfect matching (cf. Definitions and Remarks 2.6) from a complete graph K_{2n}, then the resulting graph is called a cocktail party and denoted by CP(2n).

We now state our next result, which gives us some information on the structure of the unit graphs of fields.

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.

Proof. Suppose that G(R) ≅ K_{1} ∨ CP(p^{n} − 1). Hence there exists an element r ∈ R which is adjacent to every element of R. Since G(R) is not regular, every element of R except r is invertible and hence 2 ∈ U(R) and r = 0. Therefore, R is a field with p^{n} elements.

Conversely, it is easy to see that if in the unit graph G(R), we remove the zero, then the remaining graph is a complete graph without the edge {−r, r} for every r ≠ 0. Hence this latter graph is a cocktail party and so it is isomorphic to CP(p^{n} − 1). Since the zero of R is adjacent to each nonzero elements of R, we conclude that G(R) ≅ K_{1} ∨ CP(p^{n} − 1). □

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.

4. Connectedness of unit graphs

In this section we study the connectedness of the unit graph G(R). In particular, we give a necessary and sufficient condition for G(R) to be connected, based on the unit sum number of R (cf. Definitions and Remarks 4.2 and Theorem 4.3).

Definitions and Remarks 4.1. 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. The maximal connected subgraphs of G are its connected components. Here, maximal means that including any more vertices would yield a disconnected subgraph. Any graph is a union of its connected components. If the number of connected components of G is equal to one, then G is, of course, connected.

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 clearly G(R) is a union of two copies of vertex-disjoint graph G(ℤ_{2} ×T), and therefore, G(R) is not connected. Thus unit graphs are not connected in general. In this section we study when unit graphs are connected. First, we give a necessary and sufficient condition for connectedness of G(R) based on the unit sum number of R. In order to do this, we first explain a few things about k-good rings.

Definitions and Remarks 4.2. 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 [6] 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. [1] for unit sum numbers of some other rings).

The topic of unit sum numbers seems to have arisen in 1954 with an article by Zelinsky [18] in which he shows that if V is any finite or infinite dimensional vector space over a division ring D then every linear transformation is the sum of two automorphisms unless dim V = 1 and D is the field of two elements. Interest in this topic increased recently after Goldsmith, Pabst and Scott defined the unit sum number in [6]. For additional historical background the reader is referred to the article [17], which also contains references to recent work in this area.

We now state Theorem 4.3, which contains a necessary and sufficient condition for G(R) to be connected, based on the unit sum number of R.

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

Proof. Consider

S = {a ∈ R | a is k−good for some k}.

Note that 0 is a 2-good element of R and so 0 ∈ S. (In fact, S is a subring of R.) We claim that the vertex-induced subgraph ⟨S⟩ of G(R) is a connected component of G(R). For proving the claim suppose that x ∈ S is given. Therefore x is a k-good element for some k, and so we may write x = u_{1} + … + u_{k} where u_{1}, …, u_{k} ∈ U(R). We now have the walk

0 ⟶^{e_{1}} −u_{1} ⟶^{e_{2}} u_{1} + u_{2} ⟶^{e_{3}} −u_{1} − u_{2} − u_{3} ⟶^{e_{4}} u_{1} + u_{2} + u_{3} + u_{4} ⟶ … ⟶^{e_{k}}

u_{1} + … + u_{k} = x

between 0 and x in ⟨S⟩, when k is even, and the walk

0 ⟶^{e_{1}} u_{1} ⟶^{e_{2}} −u_{1} − u_{2} ⟶^{e_{3}} u_{1} + u_{2} + u_{3} ⟶^{e_{4}} −u_{1} − u_{2} − u_{3} − u_{4} ⟶ … ⟶^{e_{k}}

u_{1} + … + u_{k} = x

between 0 and x in ⟨S⟩, when k is odd.

This implies that for every x, y ∈ S, there is a walk W_{1} between x and 0 in ⟨S⟩ as well as a walk W_{2} between 0 and y in ⟨S⟩. The walks W_{1} and W_{2} together form a walk W between x and y in ⟨S⟩. Thus, we conclude that there is also a path P between x and y in ⟨S⟩. Therefore, ⟨S⟩ is a connected subgraph of G(R).

Now suppose that x ∈ R \ S. If the vertex-induced subgraph ⟨S ∪ {x}⟩ of G(R) is still connected, then there exists a path

0 = x_{0} ⟶^{e_{1}} x_{1} ⟶^{e_{2}} x_{2} ⟶ … ⟶^{e_{k}} x_{k} ⟶^{e_{k+1}} x_{k+1} = x

between 0 and x in ⟨S ∪ {x}⟩. Thus x_{i} + x_{i−1} := u_{i} is a unit for 1 ≤ i ≤ k + 1 and so

x = \{ \begin{matrix}∑_{i=0}^{k}(−1)^{i}u_{i+1} & if k is even, \\ ∑_{i=0}^{k}(−1)^{i+1}u_{i+1} & if k is odd. \end{matrix}

Therefore, x ∈ S, a contradiction. This implies that ⟨S⟩ is a connected component of G(R).

Now it is easy to see that u(R) ≤ ω if and only if S = R. On the other hand, S = R if and only if ⟨S⟩ = G(R). Therefore, using the claim, we conclude that 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 4.3, their unit graphs are connected (see for example [8, 16]).

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.

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.

Proof. Suppose that x ∈ R \ U(R) is given. Since U(R) is a dominating set, there exists u_{1} ∈ U(R) such that x is adjacent to u_{1}. Therefore, x + u_{1} ∈ U(R), and so x is a 2-good element. This implies that u(R) ≤ ω and so by Theorem 4.3, G(R) is connected as required. □

Note that there are infinitely many rings R such that U(R) is a dominating set of G(R) and, therefore, by Corollary 4.4, 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). To show this fact, let x ∈ R \ U(R) be given. We may write x = u_{1} + u_{2}, where u_{1}, u_{2} ∈ U(R). This implies that x is adjacent to −u_{1} ∈ U(R) and, therefore, U(R) is a dominating set. It is remarkable that the converse of this fact is not correct in general. For example U(ℤ_{2}) = {1} is a dominating set of G(ℤ_{2}), but ℤ_{2} is not a 2-good ring since u(ℤ_{2}) = ω.

In the following, we study the connectedness of the unit graphs associated with certain particular types of rings. We start with rings of polynomials. For the proof of the next result, we need a well-known fact, and so we state it here for the convenience of the reader.

Fact 4.5 (cf. [9]). Let R be a commutative ring and f = a_{0} + a_{1}x + … + a_{n}x^{n} ∈ R[x]. Then f is a unit in R[x] if and only if a_{0} is a unit in R and for every i, 1 ≤ i ≤ n, a_{i} is a nilpotent element of R.

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

Proof. By Fact 4.5, if two polynomials f = a_{0} + a_{1}x + … + a_{n}x^{n} ∈ R[x] and g = b_{0} + b_{1}x + … + b_{m}x^{m} ∈ R[x] are adjacent, then necessarily each a_{i} = −b_{i} whenever i > 0 and so n = m. Therefore, if there exists a path between g_{1}, g_{2} ∈ R[x], then deg(g_{1}) = deg(g_{2}). This means that G(R[x]) is disconnected. □

The following result gives us information on the connectedness of unit graphs associated with matrix rings. Note that this result could also be deduced from Theorem 4.3, since Henriksen [8] showed that the unit sum number of the ring of n×n matrices over R, M_{n}(R), n > 1, is less than or equal to three.

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.

Proof. Suppose that A and B are two given elements of M_{n}(R). By a result due to I. Kaplansky (cf. [8, Lemma 2]), we may write A = D_{A} + U_{A} and B = D_{B} + U_{B}, where D_{A} and D_{B} are diagonal matrices in M_{n}(R) and U_{A} and U_{B} are unit elements of M_{n}(R). Therefore, A is adjacent to −D_{A} and B is adjacent to −D_{B}. Consider −D_{A} = diag(d_{1}, …, d_{n}) and −D_{B} = diag(d′_{1}, …, d′_{n}). Since |R| > 2, for each i, 1 ≤ i ≤ n, we may choose l_{i} such that l_{i} ∉ {−d_{i}, −d′_{i}}. If we now consider L = diag(l_{1}, …, l_{n}), then both of −D_{A} and −D_{B} are adjacent to L. This shows that the unit graph G(M_{n}(R)) is connected as required. □

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

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.

5. Further properties of unit graphs

In this section some characterization results regarding chromatic index, diameter, girth, and planarity of G(R) are given.

Definitions and Remarks 5.1. 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 χ′(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.

We now state the following result which shows that all unit graphs are class 1.

Theorem 5.2. Let R be a finite ring. Then the unit graph G(R) is class 1.

Proof. We color the edge xy by the color x + y. By this coloring, every two distinct edges xy and xz have different colors and C = {x + y | xy is an edge of G} is the set of colors. Therefore, G(R) has a |C|-edge coloring and so χ′(G(R)) ≤ |C|. But clearly C ⊆ U(R) and thus χ′(G(R)) ≤ |C| ≤ |U(R)|. On the other hand, Proposition 2.4 implies that Δ = |U(R)| and so by Vizing’s theorem we have χ′(G(R)) ≥ Δ = |U(R)|. Therefore χ′(G(R)) = |U(R)| = Δ and so G(R) is class 1. □

Definitions and Remarks 5.3. For a graph G and vertices x and y of G, the distance between x and y, denoted d(x, y), is the number of edges in a shortest path between x and y. If there is no any path between x and y, then we write d(x, y) = ∞. For example, let R be a ring, G(R) be the unit graph associated with R and x ∈ R. Then the proof of Theorem 4.3 shows that d(0, x) = k if and only if x is a k-good element of R but it is not a (k − 1)-good element. Also we recall that 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). One can easily see that, for example, diam(G(ℤ_{6})) = 3, diam(G(ℤ_{8})) = 2, and diam(G(ℤ)) = ∞.

The following result is an immediate consequence of the proof of Proposition 4.7.

Corollary 5.4. 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 we have diam(G(M_{n}(R))) ≤ 4.

In the following, we study the diameter of the unit graphs. By using Lemma 5.5 and Corollary 5.6, we prove Theorem 5.7 which is a characterization of diameter of the unit graph G(R).

Lemma 5.5. Let R be a finite commutative ring such that R is not a field with Char(R) = 2. Then the following statements hold:

(a) If either R cannot have ℤ_{2} as a quotient or R is a local ring with 𝔪 as the unique maximal ideal in such a way that |R/𝔪| = 2, then diam(G(R)) = 2;

(b) If R has ℤ_{2} as a quotient and R cannot have ℤ_{2}×ℤ_{2} as a quotient and R is not a local ring with 𝔪 as the unique maximal ideal in such a way that |R/𝔪| = 2, then diam(G(R)) = 3;

(c) If R has ℤ_{2} × ℤ_{2} as a quotient, then diam(G(R)) = ∞.

Proof. Since every finite commutative ring with nonzero identity is isomorphic to a direct product of finite local rings (cf. [13, Page 95]), we may write R ≅ R_{1} ×…×R_{k}, where every R_{i} is a local ring with maximal ideal 𝔪_{i}.

Now for proof of (a), assume that R cannot have ℤ_{2} as a quotient. Thus |R_{i}/𝔪_{i}| > 2 holds for every i. Suppose x = (x_{1}, …, x_{k}) and y = (y_{1}, …, y_{k}) are arbitrary distinct elements of R_{1} × … × R_{k}. Since for every i with 1 ≤ i ≤ k, we have |R_{i}/𝔪_{i}| > 2, by Remark 2.5, we conclude that N_{\overline{G}(R_{i})}(x_{i}) ∩ N_{\overline{G}(R_{i})}(y_{i}) ≠ ∅. Therefore, we may choose z_{i} ∈ N_{\overline{G}(R_{i})}(x_{i}) ∩ N_{\overline{G}(R_{i})}(y_{i}). Thus we have the following walk in \overline{G}(R_{1} × … × R_{k}):

(x_{1}, …, x_{k}) ⟶^{e_{1}} (z_{1}, …, z_{k}) ⟶^{e_{2}} (y_{1}, …, y_{k}).

This implies that d(x, y) ≤ 2 and so diam(G(R)) = diam(G(R_{1} × … × R_{k})) ≤ 2. If diam(G(R)) = 1, then G(R) is a complete graph and so by Theorem 3.4, R is a field with Char(R) = 2, a contradiction. Therefore, diam(G(R)) = 2.

Now suppose that R is a finite local ring with maximal ideal 𝔪 in such a way that |R/𝔪| = 2. By using Theorem 3.5 we conclude that G(R) is complete bipartite with |R| ≥ 4, and so diam(G(R)) = 2.

For proof of (b), since R cannot have ℤ_{2} ×ℤ_{2} as a quotient but has ℤ_{2} as a quotient, |R_{i}/𝔪_{i}| > 2 holds for every i except one of them. If k = 1, then R ≅ R_{1} is a finite local ring with maximal ideal 𝔪_{1} in such a way that |R_{1}/𝔪_{1}| = 2, a contradiction. Therefore, k ≥ 2. In this case, we may assume that |R_{1}/𝔪_{1}| = 2 and |R_{i}/𝔪_{i}| > 2 for every i with 2 ≤ i ≤ k. Suppose that x = (x_{1}, x_{2}, …, x_{k}) and y = (y_{1}, y_{2}, …, y_{k}) are arbitrary distinct elements of R_{1} × R_{2} × … × R_{k}. If either x_{1}, y_{1} ∈ 𝔪_{1} or x_{1}, y_{1} ∉ 𝔪_{1}, then by an argument similar to that above, we obtain a path between x and y with the length at most 2. This implies that d(x, y) ≤ 2. Now, we may assume that x_{1} ∈ 𝔪_{1} and y_{1} ∉ 𝔪_{1}. For every i with 2 ≤ i ≤ k, consider w_{i} as follows:

w_{i} = \{ \begin{matrix}1 & if x_{i} ∈ 𝔪_{i}, \\ 0 & if x_{i} ∉ 𝔪_{i}. \end{matrix}

On the other hand, since for every i with 2 ≤ i ≤ k we have |R_{i}/𝔪_{i}| > 2, by Remark 2.5, we conclude that N_{\overline{G}(R_{i})}(w_{i}) ∩ N_{\overline{G}(R_{i})}(y_{i}) ≠ ∅. Therefore, we may choose z_{i} ∈ N_{\overline{G}(R_{i})}(w_{i})∩N_{\overline{G}(R_{i})}(y_{i}). Thus we have the following walk in \overline{G}(R_{1}×R_{2}×…×R_{k}):

(x_{1}, x_{2}, …, x_{k}) ⟶^{e_{1}} (y_{1}, w_{2}, …, w_{k}) ⟶^{e_{2}} (x_{1}, z_{2}, …, z_{k}) ⟶^{e_{3}} (y_{1}, y_{2}, …, y_{k}).

This implies that d(x, y) ≤ 3. Therefore, for every distinct elements x, y ∈ R_{1} × R_{2} × …×R_{k}, we have d(x, y) ≤ 3 and so diam(G(R_{1} × R_{2} × … × R_{k})) ≤ 3. Now, consider two elements a = (0, 0, …, 0) and b = (1, 0, …, 0) in G(R_{1} × R_{2} × … × R_{k}). Since a and b are not adjacent, we conclude that d(a, b) ≥ 2. If d(a, b) = 2, then there must be a path

(0, 0, …, 0) ⟶^{e_{1}} (x_{1}, x_{2}, …, x_{k}) ⟶^{e_{2}} (1, 0, …, 0).

The adjacency of (0, 0, …, 0) and (x_{1}, x_{2}, …, x_{k}) implies that x_{1} is a unit element, while the adjacency of (x_{1}, x_{2}, …, x_{k}) and (1, 0, …, 0) implies that x_{1} is not a unit element, a contradiction. Therefore, d(a, b) ≥ 3 and since diam(G(R_{1} × R_{2} × … × R_{k})) ≤ 3, we conclude that diam(G(R)) = diam(G(R_{1} × R_{2} × … × R_{k})) = 3.

For (c), we have k ≥ 2, and so we may consider two elements a = (1, 1, …, 0) and b = (1, 0, …, 0) in G(R_{1} × R_{2} × … × R_{k}). If there is a path

(1, 1, …, 0) ⟶^{e_{1}} (x_{1}, x_{2}, …, x_{k}) ⟶ … ⟶^{e_{n−1}} (y_{1}, y_{2}, …, y_{k}) ⟶^{e_{n}} (1, 0, …, 0)

between a and b, then we obtain the following walks in G(R_{1}) and G(R_{2}):

1 ⟶^{e′_{1}} x_{1} ⟶ … ⟶^{e′_{n−1}} y_{1} ⟶^{e′_{n}} 1,

1 ⟶^{e′′_{1}} x_{2} ⟶ … ⟶^{e′′_{n−1}} y_{2} ⟶^{e′′_{n}} 0.

The first walk shows that n is even, while the second one shows that n is odd, a contradiction. Therefore, there is no path between a and b which implies that diam(G(R)) = diam(G(R_{1} × R_{2} × … × R_{k})) = ∞. □

The following result shows that the diameter of the unit graph of a finite commutative ring does not contain all positive integers.

Corollary 5.6. Let R be a finite commutative ring. Then we have diam(G(R)) ∈ {1, 2, 3, ∞}.

Proof. If R is a field with Char(R) = 2, then by Theorem 3.4, G(R) is a complete graph and so diam(G(R)) = 1. If R is a field with Char(R) ≠ 2, then by Theorem 3.8, diam(G(R)) = 2.

Now, we assume that R is not a field. If R has ℤ_{2} × ℤ_{2} as a quotient, then part (c) of Lemma 5.5 implies that diam(G(R)) = ∞. If R cannot have ℤ_{2} × ℤ_{2} as a quotient, then there are two possibilities: either R cannot have ℤ_{2} as a quotient or has ℤ_{2} as a quotient. In the first case, by part (a) of Lemma 5.5, we have diam(G(R)) = 2. In the second case, if R is a local ring with maximal ideal 𝔪, then |R/𝔪| = 2 and so by part (a) of Lemma 5.5, we have diam(G(R)) = 2. Otherwise, by part (b) of Lemma 5.5, we have diam(G(R)) = 3. □

The following theorem is a characterization of diameter of the unit graph G(R).

Theorem 5.7. Let R be a finite commutative ring. Then 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.

Proof. Part (a) is an immediate consequence of Theorem 3.4.

For (b), first assume that diam(G(R)) = 2. There are two possibilities: either R is a filed or not. If R is a field, then by part (a), we conclude that Char(R) ≠ 2. Thus the case (1) occurs. Therefore, we may assume that R is not a field. If R cannot have ℤ_{2} as a quotient then, of course, the case (2) occurs. Thus we may suppose that R has ℤ_{2} as a quotient. By part (c) of Lemma 5.5, R cannot have ℤ_{2} × ℤ_{2} as a quotient and so part (b) of Lemma 5.5 implies that R is a local ring with maximal ideal 𝔪 such that |R/𝔪| = 2 and R ≇ ℤ_{2}. Thus the case (3) occurs.

The converse of part (b) is an immediate consequence of Theorem 3.8 and Lemma 5.5.

For (c), first assume that diam(G(R)) = 3. Note that the proof of Corollary 5.6 implies that R is not a field. Therefore, by part (c) of Lemma 5.5, R cannot have ℤ_{2} × ℤ_{2} as a quotient. If R cannot have ℤ_{2} as a quotient, then by part (a) of Lemma 5.5, diam(G(R)) = 2, a contradiction. Thus R has ℤ_{2} as a quotient. If R is a local ring with maximal ideal 𝔪, then |R/𝔪| = 2. Thus by part (a) of Lemma 5.5, diam(G(R)) = 2, a contradiction. This completes the proof.

Part (d) and the converse of part (c) is an immediate consequence of Lemma 5.5 and Corollary 5.6. □

Remark 5.8. The finiteness of R in Theorem 5.7 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.

Definitions and Remarks 5.9. 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. If G is a bipartite graph, then G has no odd cycle and so gr(G) ≥ 4 (cf. Definitions and Remarks 3.1).

The following result shows that the girth of the unit graph of a finite commutative ring does not contain all positive integers.

Proposition 5.10. Let R be a finite commutative ring. Then we have gr(G(R)) ∈ {3, 4, 6, ∞}.

Proof. Suppose that J(R) ≠ 0, where J(R) denotes the Jacobson radical of R. Therefore we may choose two distinct elements x and y in J(R). This implies that two distinct elements 1 − x and 1 − y lie in U(R). On the other hand, every element of J(R) is adjacent to every element of U(R). Hence we obtain that gr(G(R)) ∈ {3, 4}.

Now suppose that J(R) = 0. Since every finite commutative ring with nonzero identity is isomorphic to a direct product of finite local rings (cf. [13, Page 95]), we may write R ≅ R_{1} × … × R_{k}, where every R_{i} is a local ring with maximal ideal 𝔪_{i}. If k = 1, then R is a field and so R ≅ ℤ_{2}, R ≅ ℤ_{3} or |R| ≥ 4. If R ≅ ℤ_{2} or R ≅ ℤ_{3}, then we have gr(G(R)) = ∞. If |R| ≥ 4, then we have two nonzero unit elements x and y such that x + y ≠ 0. Therefore, x and y are adjacent, and so we obtain the cycle

0 ⟶^{e_{1}} x ⟶^{e_{2}} y ⟶^{e_{3}} 0.

This implies that gr(G(R)) = 3. If k ≥ 2, then for every i with 1 ≤ i ≤ k we have J(R_{i}) = 0 and so R_{i} is a field. Therefore, we may assume that R has the form

R ≅ \underbrace{ℤ_{2} × … × ℤ_{2}}_{ℓ times} × \underbrace{ℤ_{3} × … × ℤ_{3}}_{m times} ×F_{1} × … × F_{t} × E_{1} × … × E_{s},

where Char(F_{i}) = 2, |F_{i}| ≥ 4, 1 ≤ i ≤ t and Char(E_{j}) ≥ 3, |E_{i}| ≥ 4, 1 ≤ j ≤ s, and ℓ + m + t + s = k. We consider the following cases.

Case 1: If ℓ = k. In this case, R has just one unit element and so G(R) is a 1-regular graph. Thus gr(G(R)) = ∞.

Case 2: If 0 < ℓ < k and m = 0. In this case, G(R) is a union of some copies of

G(ℤ_{2} × F_{1} × … × F_{t} × E_{1} × … × E_{s}),

where every copy is a bipartite graph. Thus gr(G(R)) ≥ 4. Now, for every i with 1 ≤ i ≤ t and j with 1 ≤ j ≤ s we choose the nonzero elements α_{i}, β_{i}, γ_{i} ∈ F_{i} and δ_{j}, η_{j} ∈ E_{j} in such a way that α_{i} + β_{i} ≠ 0, β_{i} + γ_{i} ≠ 0, and δ_{j} + η_{j} ≠ 0. Therefore, we obtain the cycle

(0, α_{1}, …, α_{t}, 0, …, 0) ⟶^{e_{1}} (1, β_{1}, …, β_{t}, η_{1}, …, η_{s}) ⟶^{e_{2}} (0, γ_{1}, …, γ_{t}, 0, …, 0) ⟶^{e_{3}}

(1, 0, …, 0, δ_{1}, …, δ_{s}) ⟶^{e_{4}} (0, α_{1}, …, α_{t}, 0, …, 0),

which implies that gr(G(R)) = 4.

Case 3: If 0 < ℓ < k and m ≠ 0. By an argument similar to case 2, we consider the unit graph

G(ℤ_{2} × \underbrace{ℤ_{3} × … × ℤ_{3}}_{m times} ×F_{1} × … × F_{t} × E_{1} × … × E_{s})

and obtain the cycle

(0, 0, …, 0, α_{1}, …, α_{t}, 0, …, 0) ⟶^{e_{1}} (1, 2, …, 2, 0, …, 0, η_{1}, …, η_{s}) ⟶^{e_{2}}

(0, 2, …, 2, β_{1}, …, β_{t}, 0, …, 0) ⟶^{e_{3}} (1, 0, …, 0, 0, …, 0, δ_{1}, …, δ_{s}) ⟶^{e_{4}}

(0, 1, …, 1, γ_{1}, …, γ_{t}, 0, …, 0) ⟶^{e_{5}} (1, 1, …, 1, 0, …, 0, η_{1}, …, η_{s}) ⟶^{e_{6}}

(0, 0, …, 0, α_{1}, …, α_{t}, 0, …, 0).

This implies that gr(G(R)) ≤ 6. But in this case, the unit graph G(R) is bipartite, and so we get gr(G(R)) ∈ {4, 6}.

Case 4: If ℓ = 0. By an argument similar to case 2, we obtain the cycle

(0, …, 0, 0, …, 0, 0, …, 0) ⟶^{e_{1}} (1, …, 1, α_{1}, …, α_{t}, δ_{1}, …, δ_{s}) ⟶^{e_{2}}

(1, …, 1, β_{1}, …, β_{t}, η_{1}, …, η_{s}) ⟶^{e_{3}} (0, …, 0, 0, …, 0, 0, …, 0).

Thus gr(G(R)) = 3. This completes the proof. □

Remark 5.11. 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.

The following result is an immediate consequence of the proof of Proposition 2.9.

Corollary 5.12. Let R be a finite commutative ring, and let M be a finite unitary R-module. Suppose that R ⊕ M denotes the Nagata extension of R by M. If |M| > 2, then we have gr(G(R ⊕ M)) ≤ 4. In particular, if 2 ∈ U(R), then gr(G(R ⊕ M)) = 3.

Definitions and Remarks 5.13. 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. A subdivision of an edge of G is obtained by inserting into this edge some new vertices of degree two. A subdivision of a graph G is the result of subdividing its edges. Further, G is also considered as a subdivision of itself. A remarkably simple characterization of planar graphs was given by Kuratowski in 1930. Kuratowski’s theorem says that a graph is planar if and only if it contains no subdivision of K_{3,3} or K_{5} (cf. Definitions and Remarks 2.6 and [3, Page 153]). Also if G is a connected planar graph with p ≥ 3 vertices and q edges, then we have q ≤ 3p − 6. Moreover, if gr(G) ≥ 4, then we have the better bound q ≤ 2p − 4. In addition, if G is a planar graph, then G contains a vertex of degree at most five. Unit graphs are not planar in general. An example to illustrate this fact is the unit graph G(ℤ_{10}), which is not planar because G(ℤ_{10}) is a 4-regular connected bipartite graph and thus has no odd cycle (cf. Definitions and Remarks 3.1). Therefore gr(G(ℤ_{10})) ≥ 4 (cf. Definitions and Remarks 5.9) and so q = 20 > 16 = 2p − 4 which, by the above observation, implies that G(ℤ_{10}) 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.

We now state our final result: a necessary and sufficient condition for the planarity of G(R). Here, 𝔽_{4} denotes the field with four elements.

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}\}.

Proof. Suppose that the unit graph G(R) is planar. We claim that |J(R)| ≤ 2, where J(R) denotes the Jacobson radical of R. To prove this, we suppose the contrary. Then |J(R)| ≥ 3. Therefore we may choose three distinct elements x, y, and z in J(R). This implies that three distinct elements 1 − x, 1 − y, and 1 − z lie in U(R). Since every element of J(R) is adjacent to every element of U(R), we obtain a graph K_{3,3} in the structure of G(R). Thus, by Kuratowski’s theorem (cf. Definitions and Remarks 5.13), the unit graph G(R) is not planar, a contradiction. Therefore, the claim holds, and we have |J(R)| ≤ 2.

On the other hand, by the observation in Definitions and Remarks 5.13, the minimum degree of vertices of G(R) is at most five. Thus Proposition 2.4 implies that |U(R)| ≤ 6.

Since every finite commutative ring with nonzero identity is isomorphic to a direct product of finite local rings (cf. [13, Page 95]), we may write R ≅ R_{1} ×…×R_{k}, where every R_{i} is a local ring with maximal ideal 𝔪_{i}. There are two cases to be considered:

(1) k = 1 and (2) k ≥ 2.

Case 1: In this case, we have k = 1 and so R (≅ R_{1}) is a local ring with maximal ideal 𝔪 (≅ 𝔪_{1}). On the other hand, by the above observation, we have |J(R)| ≤ 2 and |U(R)| ≤ 6. Thus we obtain that |𝔪| ≤ 2 and |R \ 𝔪| ≤ 6.

If |𝔪| = 1, then 𝔪 = {0} and so R is a field. Since |R\𝔪| ≤ 6, we have that |R| ≤ 7 and so R ≅ ℤ_{2}, R ≅ ℤ_{3}, R ≅ 𝔽_{4}, R ≅ ℤ_{5}, or R ≅ ℤ_{7}. The case R ≅ ℤ_{7} is ruled out since the unit graph G(ℤ_{7}) is not planar (cf. Definitions and Remarks 5.13). The other rings have planar unit graphs.

If |𝔪| = 2, then 𝔪 ≠ {0}, and so R is not a field. Since |R \ 𝔪| ≤ 6, we have that

|R| ≤ 8 and so |R| = 4 or |R| = 8. If |R| = 4, then R ≅ ℤ_{4} or R ≅ \{ [ \begin{matrix}a & b \\ 0 & a \end{matrix}] | a, b ∈ ℤ_{2}\},

which both have planar unit graphs. If |R| = 8, then R is isomorphic to one of the five local rings of order 8: R ≅ L_{i}, 1 ≤ i ≤ 5 (cf. [4]). The unit graphs associated with all of these rings are ruled out because for every i with 1 ≤ i ≤ 5, we have |J(L_{i})| = 4, and so the associated unit graphs are not planar.

Case 2: In this case, we have k ≥ 2.

If |J(R)| = 1, then for every i with 1 ≤ i ≤ k, we have |J(R_{i})| = 1 and so R_{i} is a field. On the other hand, |U(R)| ≤ 6, and so for every i with 1 ≤ i ≤ k, we have |U(R_{i})| ≤ 6. Therefore, R is isomorphic to one of the following rings:

(i) \underbrace{ℤ_{2} × … × ℤ_{2}}_{ℓ times} ×S, where ℓ > 0 and S ≅ ℤ_{2}, S ≅ ℤ_{3}, S ≅ 𝔽_{4}, S ≅ ℤ_{5}, or S ≅ ℤ_{7};

(ii) \underbrace{ℤ_{2} × … × ℤ_{2}}_{ℓ times} × ℤ_{3} × ℤ_{3}, where ℓ ≥ 0;

(iii) \underbrace{ℤ_{2} × … × ℤ_{2}}_{ℓ times} × ℤ_{3} × 𝔽_{4}, where ℓ ≥ 0.

If R is isomorphic to one the rings that appear in (i), then clearly G(R) is a union of some copies of vertex-disjoint graph G(ℤ_{2} × S). Therefore, the planarity of G(R) is equivalent to planarity of G(ℤ_{2} × S). On the other hand, both G(ℤ_{2} × ℤ_{5}) and G(ℤ_{2} × ℤ_{7}) are bipartite graphs with girth ≥ 4 and so, by Definitions and Remarks 5.13, are not planar. Thus the cases S ≅ ℤ_{5} and S ≅ ℤ_{7} among the rings appearing in (i) are ruled out. The other rings in (i) have planar unit graphs.

For rings appearing in (ii), if ℓ = 0, then we have the ring ℤ_{3} × ℤ_{3} which has planar unit graph (cf. Fig. 4). If ℓ > 0, then all rings are ruled out. To see this, we note that since the unit graph G(ℤ_{2} × ℤ_{3} × ℤ_{3}) is 4-regular with girth ≥ 4 and 36 edges, Definitions and Remarks 5.13 imply it is not planar.

All rings appearing in (iii) are ruled out. To see this, we note that the unit graph G(ℤ_{3} × 𝔽_{4}) is 6-regular, and so the minimum degree of vertices of G(ℤ_{3} × 𝔽_{4}) is six. Therefore, by Definitions and Remarks 5.13, the unit graph G(ℤ_{3} × 𝔽_{4}) is not planar.

If |J(R)| = 2, then for at most one i with 1 ≤ i ≤ k, we have |J(R_{i})| = 2. Thus R ≅ R_{1} × … × R_{k−1} × S, where every R_{i} is a field and |J(S)| = 2. Since |U(R)| ≤ 6, we conclude that |U(S)| ≤ 6. Therefore, |S| ≤ 8 and so S ≅ ℤ_{4} or S ≅ \{ [ \begin{matrix}a & b \\ 0 & a \end{matrix}] | a, b ∈ ℤ_{2}\}. By an argument similar to that above, we conclude that if

R ≅ \underbrace{ℤ_{2} × … × ℤ_{2}}_{ℓ times} ×S,

where ℓ ≥ 0 and S ≅ ℤ_{4} or S ≅ \{ [ \begin{matrix}a & b \\ 0 & a \end{matrix}] | a, b ∈ ℤ_{2}\}, then the unit graph G(R) is a planar graph. This completes the proof of the theorem. □

Acknowledgments

The authors would like to thank the referee for his/her helpful remarks which have contributed to improve the presentation of the article. The authors also express their gratitude to Professor Roger A. Wiegand for his kindness and support.

References

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

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

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

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

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

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

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

[8] M. Henriksen, Two classes of rings generated by their units, J. Algebra 31 (1974), 182–193.

[9] I. Kaplansky, Commutative Rings, The University of Chicago Press, Chicago, Ill.-London, 1974.

[10] D. König, Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Math. Ann. 77 (1916), no. 4, 453–465.

[11] D. König, Theory of Finite and Infinite Graphs, Translated from the German by R. McCoart, Birkhäuser Boston, Inc., Boston, MA, 1990.

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

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

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

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

[16] R. Raphael, Rings which are generated by their units, J. Algebra 28 (1974), 199–205.

[17] P. Vámos, 2-Good rings, Q. J. Math. 56 (2005), no. 3, 417–430.

[18] D. Zelinsky, Every linear transformation is a sum of nonsingular ones, Proc. Amer. Math. Soc. 5 (1954), 627–630.

N. Ashrafi, Department of Mathematics, Semnan University, Semnan, Iran.

  E-mail address: nashrafi@semnan.ac.ir

H. R. Maimani, Mathematics Section, Department of Basic Sciences, Shahid Rajaee Teacher Training University, 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.

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