NECESSARY AND SUFFICIENT CONDITIONS FOR UNIT GRAPHS TO BE HAMILTONIAN

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

Abstract. The unit graph corresponding to an associative ring 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 is a unit of R. By a constructive method, we derive necessary and sufficient conditions for unit graphs to be Hamiltonian.

1. Introduction

A graph is Hamiltonian if it has a cycle that 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 a special case of the traveling salesman problem. It is a problem in combinatorial optimization studied in operations research and theoretical computer science; see [6]. The only known way to determine whether a given graph has a Hamiltonian cycle is to undertake an exhaustive search, and until now no theorem giving a necessary and sufficient condition for a graph to be Hamiltonian was known. The study of Hamiltonian graphs has long been an important topic. See [8] for a survey, updating earlier surveys in this area.

Let n be a positive integer, and let ℤ_{n} be the ring of integers modulo n. Grimaldi [9] defined a graph G(ℤ_{n}) based on the elements and units of ℤ_{n}. The vertices of G(ℤ_{n}) are the elements of ℤ_{n}, and 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, the graph G(ℤ_{2m}) can be expressed as the union of φ(2m)/2 Hamiltonian cycles. 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 of G(ℤ_{p}).

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

Key words and phrases. Hamiltonian cycle, Hamiltonian graph, Finite ring.

The research of H. R. Maimani and S. Yassemi was in part supported by a grant from IPM (No.

89050211 and No. 89130213). 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).

Grimaldi [9] also concludes with some properties of the graphs G(ℤ_{p^{m}}), where p is a prime number and m ≥ 2. Recently, the authors of this paper generalized G(ℤ_{n}) to G(R), the unit graph of R, where R is an arbitrary associative ring with nonzero identity and studied the properties of this graph; see [1, 10].

By a constructive method, we derive necessary and sufficient conditions for unit graphs to be Hamiltonian.

2. Preliminaries and the main result

Throughout the paper, by a graph we mean a finite undirected graph without loops or multiple edges. Also all rings are finite commutative with nonzero identity. For undefined terms and concepts, see [15] and [3].

We first start with recalling some notions from graph theory. For a graph G and for any two vertices x and y of 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} → v_{1} → ⋯ → 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 Hamiltonian path (cycle) in G is a path (cycle) in G that visits every vertex exactly once. A graph is called Hamiltonian if it contains a Hamiltonian cycle. Also a graph G is called connected if for any vertices x and y of G there is a path between x and y.

We now define the unit graph corresponding to a ring. 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). The graphs in Figure 1 are the unit graphs of the rings indicated. 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 Figure 2.

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

Figure 1. Unit graphs of some specific rings.

We continue this section by collecting some notions from ring theory. First of all, for a given ring R, the Jacobson radical J(R) of R is defined to the intersection of

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

Figure 2. Unit graphs of two isomorphic rings.

all maximal ideals of R. Let R be a ring and let 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 [7], 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 u(R) of R is given by

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

• ω 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), and

• ∞ 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}) = ∞ — see [2] for unit sum numbers of some other rings. The topic of unit sum numbers seems to have arisen with a paper by Zelinsky [16], 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 [7] defined the unit sum number. For additional historical background, see [14], which also contains references to recent work in this area.

We are now ready to state the main result of this paper. The proof is given in Section 3 by a sequence of lemmas and propositions.

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.

3. The proofs

In this section we state and prove some lemmas that will be used in the proof of Theorem 2.1. For the convenience of the reader we state without proof a few known results in the form of propositions that will be used in the proofs. We also recall some definitions and notations for later use.

A bipartite graph is one whose vertex-set is partitioned into two (not necessarily nonempty) disjoint subsets so that the two end vertices for each edge lie in distinct partitions. Among bipartite graphs, a complete bipartite graph is one in which each vertex is joined to every vertex that is not in the same partition. The complete bipartite graph with two partitions of size m and n is denoted by K_{m,n}.

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

Proposition 3.1 ([1], Theorem 3.5). Let R be a ring and 𝔪 be a maximal ideal of R such that |R/𝔪| = 2. Then G(R) is a bipartite graph. The unit graph G(R) is a complete bipartite graph if and only if R is a local ring.

The degrees of all vertices of a unit graph is given by the following result. For a graph G and for a vertex x of G, the degree deg(x) of x is the number of edges of G incident with x.

Proposition 3.2 ([1], Proposition 2.4). Let R be a ring. Then the following statements hold for the unit graph of R:

(1) If 2 ∉ U(R), then deg(x) = |U(R)| for every x ∈ R.

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

We also need the following well known result due to Dirac, which initiated the study of Hamiltonian graphs. This work was continued by Ore [12].

Proposition 3.3 ([5], Theorem 3). If G is a graph with n vertices, n ≥ 3, and every vertex has degree at least n/2, then G is Hamiltonian.

Lemma 3.4. Let R be a local ring with |R| ≥ 4. Then the unit graph G(R) is Hamiltonian.

Proof. Suppose 𝔪 is the unique maximal ideal of R. There are two possibilities: either |R/𝔪| = 2 or |R/𝔪| > 2.

First, suppose that |R/𝔪| = 2. In this case, Proposition 3.1 implies that the unit graph G(R) is a complete bipartite graph. Moreover, its proof shows that 𝔪 and R\𝔪 are the partite sets of G(R). Since |R/𝔪| = 2, we conclude that |𝔪| = |R \ 𝔪| and so G(R) ≅ K_{|𝔪|,|𝔪|}. The assumptions |R| ≥ 4 and |R/𝔪| = 2 imply that |𝔪| ≥ 2 and thus G(R) is Hamiltonian.

Second, suppose that |R/𝔪| > 2. In this case, Proposition 3.2 implies that deg(x) ≥ |U(R)| − 1 for all x ∈ R. We claim that |U(R)| − 1 ≥ |R|/2. To show this, note that R is a local ring with |R| ≥ 4. If |R| = 4, then the assumption |R/𝔪| > 2 implies that |𝔪| < 2 and so 𝔪 = 0. Therefore R is a field and so |U(R)| = 3. Thus |U(R)| − 1 = 2 = |R|/2. If |R| = 5, then R is again a field and so |U(R)| = 4. Thus |U(R)| − 1 = 3 > 2.5 = |R|/2. If |R| ≥ 6, then since R is local with |R/𝔪| > 2, we conclude that |U(R)| ≥ 2|R|/3. Therefore |U(R)| − 1 ≥ (2|R|/3) − 1 ≥ |R|/2. Thus the claim holds and so deg(x) ≥ |R|/2 for every x ∈ R. Therefore Proposition 3.3 implies that G(R) is Hamiltonian. □

The following result gives us information about the existence of a Hamiltonian cycle in unit graphs of the direct product of a ring and a field.

Lemma 3.5. Let T be a ring with Hamiltonian unit graph and let F be a field. If F ≇ ℤ_{2}, then the unit graph G(T × F) is Hamiltonian.

Proof. Since the unit graph G(T) is Hamiltonian, there is a Hamiltonian cycle with length n = |T | in G(T), say

0 = a_{1} → a_{2} → ⋯ → a_{n−1} → a_{n} → a_{n+1} = 0.

Either the characteristic of F is equal to 2 or it is not.

First, suppose the latter. In this case we may assume that

F = {0, x_{1}, …, x_{(|F |−1)/2}, −x_{1}, …, −x_{(|F |−1)/2}}.

If n is even and |F | ≥ 5, then x_{2} ≠ −x_{1} and so x_{1} + x_{2} is a unit element of F. Now consider the following paths in the unit graph G(T × F):

P_{0} : (0, 0) → (a_{2}, x_{1}) → (a_{3}, 0) → (a_{4}, x_{1}) → ⋯ → (a_{n}, x_{1}),
P_{1} : (0, x_{2}) → (a_{2}, 0) → (a_{3}, x_{2}) → ⋯ → (a_{n−1}, x_{2}) → (a_{n}, 0),
P_{2} : (0, x_{1}) → (a_{2}, x_{2}) → (a_{3}, x_{1}) → ⋯ → (a_{n}, x_{2}).

Also for every i with 3 ≤ i ≤ (|F | − 1)/2, consider the path

P_{i} : (0, x_{i}) → (a_{2}, x_{i}) → (a_{3}, x_{i}) → ⋯ → (a_{n}, x_{i}),

and for every i with 1 ≤ i ≤ (|F | − 1)/2, consider the path

P′_{i} : (0, −x_{i}) → (a_{2}, −x_{i}) → ⋯ → (a_{n}, −x_{i}).

It is easy to see that P_{i−1} is adjacent to P_{i} for every i with 1 ≤ i ≤ (|F | − 1)/2 and P′_{i−1} is adjacent to P′_{i} for every i with 2 ≤ i ≤ (|F | − 1)/2, and P_{(|F |−1)/2} is adjacent to P′_{1}. Therefore P_{0}P_{1}P_{2}P_{3} ⋯ P_{(|F |−1)/2}P′_{1} ⋯ P′_{(|F |−1)/2}(0, 0) is a Hamiltonian cycle in the unit graph G(T ×F), which shows that it is Hamiltonian. If n is even and |F | = 3, then F ≅ ℤ_{3} and thus the cycle

(a_{1}, 1) → (a_{2}, 0) → (a_{3}, 2) → (a_{4}, 2) → (a_{3}, 0)

→ (a_{2}, 1) → (a_{3}, 1) → ⋯ → (a_{n−2}, 1) → (a_{n−1}, 1)

→ (a_{1}, 2) → (a_{2}, 2) → (a_{1}, 0) → (a_{n}, 1) → (a_{1}, 1),

is a Hamiltonian cycle in the unit graph G(T × F), and thus it is Hamiltonian. If n is odd and |F | ≥ 5, consider the path

P_{0} : (a_{1}, 0) → (a_{2}, x_{1}) → ⋯ → (a_{n}, 0) → (a_{1}, x_{1}) → (a_{2}, 0) → ⋯ → (a_{n}, x_{1}), and for 1 ≤ i ≤ (|F | − 1)/2 consider the paths

\begin{matrix}P_{i} : (a_{1}, x_{i}) → (a_{2}, x_{i}) → ⋯ → (a_{n}, x_{i}), \\ P′_{i} : (a_{1}, −x_{i}) → (a_{2}, −x_{i}) → ⋯ → (a_{n}, −x_{i}). \end{matrix}

It is easy to see that P_{0}P_{1} ⋯ P_{(|F |−1)/2}P′_{1} ⋯ P′_{(|F |−1)/2}(a_{1}, 0) is a Hamiltonian cycle in the unit graph G(T × F) and thus it is Hamiltonian. If n is odd and |F | = 3, we may obtain a Hamiltonian cycle in the unit graph G(T × F) by replacing the eleven end-vertices in the cycle above with

(a_{n−3}, 1) → (a_{n−2}, 1) → (a_{n−1}, 0) → (a_{n}, 2) → (a_{n−1}, 1)

→ (a_{n}, 1) → (a_{1}, 0) → (a_{2}, 2) → (a_{1}, 2) → (a_{n}, 0) → (a_{1}, 1).

This shows that the unit graph G(T × F) is Hamiltonian.

Second, suppose that characteristic of F is equal to 2. Therefore we have |F | ≥ 4. In this case we may assume that

F = {x_{1}, …, x_{2^{m}}} = {x_{2i−1}, x_{2i} | 1 ≤ i ≤ 2^{m−1}}.

If n is even, then for every i with 1 ≤ i ≤ 2^{m−1}, consider the following paths in the unit graph G(T × F):

\begin{matrix}P_{i} : (a_{1}, x_{2i−1}) → (a_{2}, x_{2i}) → ⋯ → (a_{n}, x_{2i}), \\ P′_{i} : (a_{1}, x_{2i}) → (a_{2}, x_{2i−1}) → ⋯ → (a_{n}, x_{2i−1}). \end{matrix}

Since |F | ≥ 4, it is clear that P_{1}P′_{2^{m−1}}P_{2}P′_{2^{m−1}−1} ⋯ P_{2^{m−1}}P′_{1}(0, x_{1}) is a Hamiltonian cycle in the unit graph G(T × F) and thus it is Hamiltonian.

If n is odd, then consider the path

P_{i} : (a_{1}, x_{2i−1}) → (a_{2}, x_{2i}) → ⋯ → (a_{n−1}, x_{2i}) → (a_{n}, x_{2i−1}) → ⋯ → (a_{n}, x_{2i}).

Therefore P_{1}P_{2} ⋯ P_{2^{m−1}}(a_{1}, x_{1}) is a Hamiltonian cycle in the unit graph G(T × F) and thus it is Hamiltonian. □

In the sequel we need Lemmas 3.7, 3.8 and 3.10. But first, we state the following proposition, which is useful in the proof of Lemma 3.7. Recall that a clique of a graph G is a complete subgraph of G. Also a coclique (also called an independent set of vertices) in a graph G is a set of pairwise nonadjacent vertices.

Proposition 3.6 ([1], Lemma 2.7). Let R be a ring and suppose that J(R) denotes the Jacobson radical of R. Suppose x, y ∈ R.

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

(b) If 2x ∈ U(R), then x + J(R) is a clique in the unit graph G(R).

(c) If 2x ∉ U(R), then x + J(R) is a coclique in the unit graph G(R).

Lemma 3.7. Let T be a ring and let R be a local ring with unique maximal ideal 𝔪. If the unit graph G(T × R/𝔪) is Hamiltonian, then the unit graph G(T × R) is Hamiltonian.

Proof. Since the unit graph G(T × R/𝔪) is Hamiltonian, there is a Hamiltonian cycle in G(T × R/𝔪), say

(a_{1}, y_{1} + 𝔪) → ⋯ → (a_{n}, y_{n} + 𝔪) → (a_{1}, y_{1} + 𝔪),

where n = |T × R/𝔪|. Let 𝔪 = {x_{1}, …, x_{t}}. Therefore for every i with 1 ≤ i ≤ t, we have y_{i}+𝔪 = {y_{i}+x_{1}, …, y_{i}+x_{t}} and so T ×R = ⋃_{i=1}^{n} M_{i}, where M_{i} = {(a_{i}, y_{i}+x_{j}) | 1 ≤ j ≤ t}. It is easy to see that for every r with 1 ≤ r ≤ n − 1, every element of M_{r} is adjacent to every element of M_{r+1}. Also every element of M_{n} is adjacent to every element of M_{1}. Let S_{r} for 1 ≤ r ≤ n−1 be a subgraph of the unit graph G(T ×R) with vertex-set M_{r} ∪ M_{r+1} and edge-set {(a_{r}, y_{r} + x_{j}) → (a_{r+1}, y_{r+1} + x_{ℓ}) | 1 ≤ j, ℓ ≤ t}. Also let S_{n} be a subgraph of the unit graph G(T × R) with vertex-set M_{n} ∪ M_{1} and edge-set {(a_{n}, y_{n} + x_{j}) → (a_{1}, y_{1} + x_{ℓ}) | 1 ≤ j, ℓ ≤ t}. It is easy to see that S_{r} for 1 ≤ r ≤ n is a Hamiltonian complete bipartite subgraph of the unit graph G(T × R). For every r with 1 ≤ r ≤ n − 1, let P_{r} be a Hamiltonian path of S_{r} with initial vertex (a_{r}, y_{r} + x_{1}) and the end point (a_{r+1}, y_{r+1} + x_{1}). Also let P_{n} be a Hamiltonian path of S_{n} with initial vertex (a_{n}, y_{n} + x_{1}) and end point (a_{1}, y_{1} + x_{1}). Now we consider the following two cases:

Case 1: n is even. In this case, the cycle

P_{1} → P_{3} → ⋯ → P_{n−1} → (a_{1}, y_{1} + x_{1})

is a Hamiltonian cycle in the unit graph G(T × R) and thus it is Hamiltonian.

Case 2: n is odd. In this case, since |T × R/𝔪| is odd, |R/𝔪| is odd. This implies that |R| is odd and so 2 ∈ U(R). We may assume that y_{1} + 𝔪 = 𝔪. Therefore y_{n} + 𝔪 ≠ 𝔪. Now Proposition 3.6 implies that the subgraph induced by M_{n} is a clique. Therefore the cycle

P_{1} → P_{3} → ⋯ → P_{n−2} → (a_{n}, y_{n} + x_{1}) → ⋯ → (a_{n}, y_{n} + x_{t}) → (a_{1}, y_{1} + x_{1})

is a Hamiltonian cycle in the unit graph G(T × R) and thus it is Hamiltonian. □

Lemma 3.8. Let R ≅ R_{1} × ⋯ × R_{n}, where every R_{i} is a local ring with maximal ideal 𝔪_{i}. Suppose that R ≇ ℤ_{3} and for every i with 1 ≤ i ≤ n, we have R_{i}/𝔪_{i} ≇ ℤ_{2}. Then the unit graph G(R) is Hamiltonian.

Proof. We prove the lemma by induction on n. If n = 1, then R is local and assumptions imply that |R| ≥ 4. Therefore by using Lemma 3.4 we conclude that the unit graph G(R) is Hamiltonian. Now suppose that the lemma holds true for n − 1. Consider T = R_{1} × ⋯ × R_{n−1} and F = R_{n}/𝔪_{n}. There are two possibilities: either T ≅ ℤ_{3} or T ≇ ℤ_{3}.

First, suppose that T ≅ ℤ_{3}. If |R_{n}| ≥ 4, then by Lemma 3.5 the unit graph G(R) ≅ G(ℤ_{3} × R_{n}) is Hamiltonian. If |R_{n}| = 3, then R_{n} ≅ ℤ_{3} and so R ≅ ℤ_{3} × ℤ_{3}. Therefore the cycle

(0, 0) → (1, 1) → (0, 1) → (2, 1) → (2, 0) → (2, 2) → (0, 2) → (1, 0) → (1, 2) → (0, 0),

is a Hamiltonian cycle in the unit graph G(R) ≅ G(ℤ_{3}×ℤ_{3}) and thus it is Hamiltonian.

Second, suppose that T ≇ ℤ_{3}. In this case the induction hypothesis implies that the unit graph G(T) is Hamiltonian. On the other hand, F ≅ R_{n}/𝔪_{n} is a field with |F | ≥ 3. Therefore Lemma 3.5 implies that the unit graph G(T × F) is Hamiltonian. Therefore by applying Lemma 3.7, we conclude that the unit graph G(R) is Hamiltonian. □

We need the following result to give a proof of Lemma 3.10.

Proposition 3.9 ([4], Theorem 8.6). Let G be a bipartite graph with partite sets X and Y such that |X| = |Y | = n ≥ 2. If deg(x) > n/2 for every vertex x of G, then G is Hamiltonian.

Lemma 3.10. Let R ≅ R_{1} × ⋯ × R_{n} × ℤ_{2}, where every R_{i} is a local ring with maximal ideal 𝔪_{i}. If R_{i}/𝔪_{i} ≇ ℤ_{2} for every i with 1 ≤ i ≤ n, then the unit graph G(R) is Hamiltonian.

Proof. We prove the lemma by induction on n. If n = 1, then R ≅ R_{1} × ℤ_{2}. In this case, it is easy to see that the unit graph G(R) is a bipartite graph with partite sets X = R_{1} × {0} and Y = R_{1} × {1}. On the other hand, by Proposition 3.2(1), we have deg(x) = |U(R)| = |U(R_{1})| > |U(R_{1})|/2 ≥ |R|/4 for every vertex x in G(R). Therefore, by Proposition 3.9, the unit graph G(R) is Hamiltonian.

Now suppose that the lemma holds for n − 1. The induction hypothesis implies that the unit graph G(R_{1} × ⋯ × R_{n−1} × ℤ_{2}) is Hamiltonian. On the other hand, F ≅ R_{n}/𝔪_{n} is a field with |F | ≥ 3. Therefore Lemma 3.5 implies that the unit graph G(R_{1}×⋯×R_{n−1}×ℤ_{2}×F) is Hamiltonian and so by applying Lemma 3.7 we conclude that the unit graph G(R) is Hamiltonian. □

A cycle graph is a graph that consists of a single cycle. The following result characterizes the unit graphs of rings that are cycle graphs.

Proposition 3.11 ([1], Theorem 3.2). Let R be a ring. Then the unit graph G(R) is a cycle graph if and only if R is isomorphic to either

(a) ℤ_{4},

(b) ℤ_{6}, or

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

The next result gives a sufficient condition for a unit graph to be Hamiltonian.

Lemma 3.12. Let R be a ring such that R ≇ ℤ_{2} and R ≇ ℤ_{3}. If R cannot have ℤ_{2} × ℤ_{2} as a quotient, then the unit graph G(R) is Hamiltonian.

Proof. Every ring is isomorphic to a direct product of local rings; see [11, Page 95]. Therefore we may write R ≅ R_{1} × ⋯ × R_{n}, where every R_{i} is a local ring with maximal ideal 𝔪_{i}. We claim that |U(R)| ≥ 2. To show this, suppose to the contrary that |U(R)| = 1. This implies that |J(R)| = 1, where J(R) denotes the Jacobson radical of R. Therefore |𝔪_{1} × ⋯ × 𝔪_{n}| = 1 and so |𝔪_{i}| = 1 for every i with 1 ≤ i ≤ n. Therefore R_{i} for 1 ≤ i ≤ n is a field and thus R ≅ ℤ_{2} × ⋯ × ℤ_{2}, where ℤ_{2} occurs n times in the product. Now the assumption implies that R ≅ ℤ_{2}, a contradiction. Thus the claim holds and we have |U(R)| ≥ 2.

First, suppose |U(R)| = 2. In this case, by Proposition 3.2, the unit graph G(R) is a 2-regular connected graph and so is a cycle graph. Hence by Proposition 3.11, R is isomorphic to either ℤ_{4}, ℤ_{6}, or \{ [ \begin{matrix}a & b \\ 0 & a \end{matrix}] | a, b ∈ ℤ_{2}\}. It is easy to see that the unit graph of each of them is Hamiltonian and therefore so is the unit graph G(R).

Second, suppose that |U(R)| ≥ 3. By the assumption, R_{i}/𝔪_{i} ≇ ℤ_{2} for every i, except for possibly at most one i. If R_{i}/𝔪_{i} ≇ ℤ_{2} for every i, then by Lemma 3.8 the unit graph G(R) is Hamiltonian. If for one i, say n, we have R_{n}/𝔪_{n} ≅ ℤ_{2}, then by Lemma 3.10 the unit graph G(R_{1} × ⋯ × R_{n} × ℤ_{2}) is Hamiltonian. Now by applying Lemma 3.7 we conclude that the unit graph G(R) is Hamiltonian. □

Proof of Theorem 2.1. (a) implies (b): By assumption, the unit graph G(R) is Hamiltonian and so it is obviously connected. Therefore, by [1, Theorem 4.3], we have u(R) ≤ ω. This means that the ring R is generated by its units and thus by [13, Corollary 7] it cannot have ℤ_{2} × ℤ_{2} as a quotient.

(b) implies (a): This holds by Lemma 3.12.

(b) is equivalent to (c): This holds by [13, Corollary 7].

(c) is equivalent to (d): This is true by definition.

(d) is equivalent to (e): This holds by [1, Theorem 4.3]. □

Acknowledgments

The authors would like to thank the referee for carefully reading the paper and for his/her suggestions. Part of this work was done while M. R. Pournaki 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 and August 2007 and January 2010. Especially he thanks Professor Rajendra Bhatia for the hospitality enjoyed at ISID.

References

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

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

[3] M. F. Atiyah, I. G. Macdonald, Introduction to Commutative Algebra, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont. 1969.

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

[5] G. A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. (3) 2 (1952), 69–81.

[6] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, San Francisco, CA, 1979.

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

[8] R. J. Gould, Advances on the Hamiltonian problem – a survey, Graphs Combin. 19 (2003), no. 1, 7–52.

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

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

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

[12] O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960), 55.

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

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

[15] D. B. West, Introduction to Graph Theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996.

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

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/

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

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