# Zero Divisor Graph for the Ring of Eisenstein Integers Modulon

Authors: Osama Alkam; Emad Abu Osba
Journal: Algebra
 (2014)

---

## Abstract

LetE
n be the ring of Eisenstein integers modulo n. In this paper we study the zero divisor graph Γ
(
E
n
). We find the diameters and girths for such zero divisor graphs and characterize n for which the graph Γ
(
E
n
) is complete, complete bipartite, bipartite, regular, Eulerian, Hamiltonian, or chordal.


---

## Body

## 1. Introduction

Letω be a primitive third root of unity. Then the set of complex numbers a
+
b
ω, where a
,
b are integers, is called the set of Eisenstein integers and is denoted by E. Since E is a subring of the field of complex numbers, it is an integral domain. Moreover, the mapping N
(
a
+
b
ω
)
=
a
2
+
b
2
-
a
b is a Euclidean norm on E. Thus E is a principal ideal domain. The units of E are ±
1, ±
ω, and ±
ω
¯. The primes of E (up to a unit multiple) are the usual prime integers that are congruent to 2 modulo 3 and Eisenstein integers whose norm is a usual prime integer. It is easily seen that, for any positive integer n, the factor ring E
/
n
E is isomorphic to the ring E
n
=
a
+
b
ω
∣
a
,
b
∈
Z
n. Thus E
n is a principal ideal ring. This ring is called the ring of Eisenstein integers modulo n. In [1] this ring is studied and its properties are investigated; its units are characterized and counted. Thus, its zero divisors are completely characterized and counted. This characterization uses the fact that a
+
b
ω is a unit in E
n if and only if N
(
a
+
b
ω
)
¯ is a unit in Z
n. Recall that a ring is local if it has a unique maximal ideal. The following are sample results of [1].(1)
Ifp is a prime integer, then the ring E
p
k is local if and only if p
=
3 or p
≡
2
(
mod
⁡
3
).
(2)
Letφ
(
R
) denote the number of units in a ring R; then
(i)
φ
(
E
3
k
)
=
2
×
3
2
k
-
1;
(ii)
φ
(
E
p
k
)
=
p
2
k
-
2
(
p
2
-
1
)
if
p
≡
2
(
mod
⁡
3
)
(
p
k
-
p
k
-
1
)
2
if
p
≡
1
(
mod
⁡
3
).We deduce the following.Proposition 1.
Letn
=
3
k
∏
i
=
1
k
p
i
α
i
∏
i
=
1
m
q
i
β
i, where k, α
i, β
i
≥
0, p
i, and q
i are primes such that p
i
≡
2
(
mod
⁡
3
), q
i
≡
1
(
mod
⁡
3
), for each i. Then
(1)
φ
E
n
=
2
×
3
2
k
-
1
∏
i
=
1
l
p
i
2
α
i
-
2
p
i
2
-
1
∏
i
=
1
m
q
i
β
i
-
q
i
β
i
-
1
2
.Proof.
Ifn
=
3
k
∏
i
=
1
l
‍
p
i
α
i
∏
i
=
1
m
‍
q
i
β
i, then E
n
≅
E
3
k
∏
i
=
1
l
‍
E
p
i
α
i
∏
i
=
1
m
‍
E
q
i
β
i. Thus, φ
(
E
n
)
=
φ
(
E
3
k
)
∏
i
=
1
l
φ
(
E
p
i
α
i
)
∏
i
=
1
m
φ
(
E
q
i
β
i
)
=
2
×
3
2
k
-
1
∏
i
=
1
l
p
i
2
α
i
-
2
(
p
i
2
-
1
)
∏
i
=
1
m
(
q
i
β
i
-
q
i
β
i
-
1
)
2.SinceE
n is a finite commutative ring with identity, every element of E
n is a unit or a zero divisor. Let Z
*
R denote the number of nonzero zero divisors of a ring R. Then(1)
Z
*
(
E
3
k
)
=
3
2
k
-
1
-
1;
(2)
Z
*
(
E
p
k
)
=
p
2
k
-
2
-
1 if p
≡
2
(
mod
⁡
3
);
(3)
Z
*
(
E
q
k
)
=
q
2
k
-
2
(
2
q
-
1
) if q
≡
1
(
mod
⁡
3
);
(4)
ifn
=
3
k
∏
i
=
1
k
‍
p
i
α
i
∏
i
=
1
m
‍
q
i
β
i, then
(2)
Z
*
E
n
=
n
-
2
×
3
2
k
-
1
∏
i
=
1
l
p
i
2
α
i
-
2
p
i
2
-
1
∏
i
=
1
m
q
i
β
i
-
q
i
β
i
-
1
2
-
1
.The (undirected) zero divisor graphΓ
(
R
) of a commutative ring R with identity that has finitely many zero divisors is the graph in which the vertices are the nonzero zero divisors of R. Two vertices are adjacent if they are distinct and their product is 0. The concept of a zero divisor graph was introduced by Beck in [2] and then studied by Anderson and Naseer in [3] in the context of coloring. The definition of zero divisor graphs in its present form was given by Anderson and Livingston in [4]. Numerous results about zero divisor graphs were obtained by Akbari et al. (see [5–7]). The zero divisor graph Γ
(
E
n
) is studied to get a better understanding of the algebraic structure of the ring E
n. The interplay of the algebraic properties of E
n, graph theoretic properties of Γ
(
E
n
), and its relation with n is studied. An earlier study was carried out for the zero divisor graph Γ
(
Z
n
[
i
]
) of the ring of Gaussian integers modulo n (see [8]). For distinct x
,
y in Z
*
(
R
), we use d
(
x
,
y
) to denote the length of the shortest path from x to y. The diameter diam
⁡
(
Γ
(
R
)
) of the graph Γ
(
R
) is defined by diam
⁡
(
Γ
(
R
)
)
=
sup
⁡
⁡
{
d
(
x
,
y
)
:
x
,
y are distinct elements of Z
*
(
R
)
}. The girth g
(
Γ
(
R
)
) of the graph Γ
(
R
) is ∞ if the graph contains no cycles; otherwise it is the length of the shortest cycle. It is shown in [4] that, for any commutative ring with identity, there is a path between any two vertices of Γ
(
R
) and that diam
⁡
(
Γ
(
R
)
)
≤
3. It is shown in [9] that the girth of the zero divisor graph of a commutative ring with identity is either 3, 4, or ∞. Throughout this paper we will use p to denote a usual prime integer that is congruent to 2 modulo 3 and use q to denote other prime integers.


## 2. Diameter and Girth of the Zero Divisor Graph ofE
q
k

In this section we find the diameter and girth of the zero divisor graphs ofE
q where q
=
3 or q is a usual prime integer congruent to 1 modulo 3. If q
=
3 and k
=
1, then Z
*
(
E
3
k
)
=
2. In fact, Z
*
(
E
3
)
=
{
2
+
ω
,
1
+
2
ω
}. These two zero divisors are adjacent. Thus, Γ
(
E
3
)
=
K
2. Hence, diam
⁡
(
Γ
(
E
3
)
)
=
1. If q
=
3 and k
>
1, then the ring E
q
k is local with the unique maximal ideal 2
+
ω. This ideal constitutes the zero divisors of E
q
k. By Corollary  2.7 in [4], there is a vertex of Γ
(
E
3
k
) adjacent to every other vertex. Hence, diam
⁡
(
Γ
(
E
3
k
)
)
≤
2. Moreover, Γ
(
E
3
k
) is not the complete graph because the vertices 3 and 2
+
ω are not adjacent. This implies that diam
⁡
(
Γ
(
E
3
k
)
)
>
1. Hence, diam
⁡
(
Γ
(
E
3
k
)
)
=
2. The following are cycles of length 3 in Γ
(
E
3
k
):3
-
-
-
3
+
3
ω
-
-
-
3
ω
-
-
-
3  if  k
=
2;
3
k
-
1
ω
-
-
-
3
-
-
-
3
k
-
1
-
-
-
3
k
-
1
ω  if  k
>
2.Thus, ifk
>
1, then g
(
Γ
(
E
3
k
)
)
=
3. These results are summarized in the following.Theorem 2.
(1)diam
⁡
(
Γ
(
E
3
k
)
)
=
1
i
f
k
=
1
2
i
f
k
>
1.
(2) Ifk
>
1, then g
(
Γ
(
E
3
k
)
)
=
3.Now we find the diameter and the girth ofΓ
(
E
q
k
), where q is a prime congruent to 1 modulo 3. Let q be such a prime. Then, there exist nonassociate Eisenstein primes a
+
b
ω and a
+
b
ω
¯ such that q
=
(
a
+
b
ω
)
(
a
+
b
ω
¯
). The ring E
q
k is the product of the two rings E
/
(
a
+
b
ω
)
k and E
/
(
a
+
b
ω
¯
)
k (see [1], page 5, Section 3) and the ideals a
+
b
ω and a
+
b
ω
¯ are the only maximal ideals of E
q
k. These two (maximal) ideals constitute the zero divisors of E
q
k.Recall that a graphΓ is bipartite if the set of vertices of Γ can be split into two disjoint sets A and B so that each edge of Γ joins a vertex of A to a vertex of B. A bipartite graph is complete bipartite if each element in A is adjacent to every element in B and conversely. It is well known that a simple graph is bipartite if and only if it contains no odd cycles (see [10]). Thus, if a simple bipartite graph contains a cycle, then its girth is 4.Lemma 3.
If a ringR is a product of two integral domains, then the graph Γ
(
R
) is complete bipartite.Proof.
See Example 2.1 (c) in [11].Lemma 4.
LetR
=
R
1
×
R
2, where R
1 and R
2 are commutative rings with identity. Then diam
⁡
(
Γ
(
R
)
)
=
3.Proof.
See [12].Theorem 5.
Letq be a prime integer congruent to 1 modulo 3. Then(1)
diam
⁡
(
Γ
(
E
q
k
)
)
=
2
i
f
k
=
1
3
i
f
k
>
1;
(2)
g
(
(
E
q
k
)
)
=
4
i
f
k
=
1
3
i
f
k
>
1.Proof.
The ringE
q is a product of two fields. Therefore, the graph Γ
(
R
) is complete bipartite. Hence, diam
⁡
(
Γ
(
E
q
)
)
=
2 and g
(
Γ
(
E
q
)
)
=
4. Let k
>
1. Since q
≡
1
(
mod
⁡
3
), there exist integers a and b such that q
=
a
2
+
b
2
-
a
b
=
(
a
+
b
ω
)
(
a
+
b
ϖ
). The ring E
q
k is isomorphic to the product of the local rings E
/
(
a
+
b
ω
)
k and E
/
(
a
+
b
ϖ
)
k. These local rings are commutative with identity and, since k
>
1, each of them contains nonzero zero divisors. Therefore, by Lemma 4, diam
⁡
(
Γ
(
E
q
)
)
=
3. To show that g
(
Γ
(
E
q
k
)
)
=
3 whenever k
>
1, it suffices to find a cycle of length 3. The following are cycles of length 3 for k
=
2 and k
>
2, respectively.q
-
-
-
q
+
q
ω
-
-
-
q
ϖ
-
-
-
q.
q
k
-
1
ω
-
-
-
q
-
-
-
q
k
-
1
-
-
-
q
k
-
1
ω.


## 3. Diameter and Girth of the Zero Divisor Graph ofE
p
k; p
≡
2
mod
⁡
3

Theorem 6.
Letp be a prime integer congruent to 2 modulo 3. Then the zero divisor graph Γ
E
p is the empty graph. If k
>
1, then(1)
diam
⁡
(
Γ
(
E
p
k
)
)
=
1
i
f
k
=
2
2
i
f
k
>
2;
(2)
g
(
Γ
(
E
p
k
)
)
=
3.Proof.
Letp be a prime integer congruent to 2 modulo 3. Then p is an Eisenstein prime integer. Hence E
p is a field. Thus, the zero divisor graph Γ
(
E
p
) is the empty graph. If k
>
1, then the ring E
p
k is local with unique maximal ideal p. This ideal constitutes the zero divisors of E
p
k. By Corollary  2.7 in [4], there is a vertex of Γ
(
E
p
k
) adjacent to every other vertex. Hence, diam
⁡
(
Γ
(
E
p
k
)
)
≤
2. Clearly when k
=
2, Γ
(
E
p
k
) is a complete graph. Thus, diam
⁡
(
Γ
(
E
p
2
)
)
=
1 and g
(
Γ
(
E
p
2
)
)
=
3. Let k
>
2. Then, p and p
ω are not adjacent. Hence, Γ
(
E
p
k
) is not a complete graph. This implies that diam
⁡
(
Γ
(
E
p
k
)
)
>
1. Hence, diam
⁡
(
Γ
(
E
p
k
)
)
=
2. The following are cycles of length 3 in Γ
(
E
p
k
):p
-
-
-
p
+
p
ω
-
-
-
p
ω
-
-
-
p if k
=
2;
p
k
-
1
ω
-
-
-
p
-
-
-
p
k
-
1
-
-
-
p
k
-
1
ω if k
>
2. Thus, if k
>
1, then g
(
Γ
(
E
p
k
)
)
=
3.This completes the proof.


## 4. Zero Divisor Graph ofE
n

We start with finding the diameter and girth of the graphΓ
(
E
n); then we characterize n for which Γ
(
E
n) is complete, complete bipartite, bipartite, regular, Eulerian, Hamiltonian, or chordal.


### 4.1. Diameter and Girth

Theorem 7.
diam
⁡
(
Γ
(
E
n
)
) equals 1 if and only if n
=
3 or n
=
p
2 and equals 2 if and only if n
=
3
k for some k
>
1, n
=
p
k for some k
>
2, n
=
q, or n
=
p
1
p
2. Otherwise diam
⁡
(
Γ
(
E
n
)
) equals 3.Proof.
Let us say that a positive integern
>
1 is of type 1 if n
=
3 or n
=
p
2, type 2 if n
=
3
k for some k
>
1 or n
=
p
k for some k
>
2 or n
=
q or n
=
p
1
p
2, and type 3 otherwise. If n
=
p
1
p
2, then E
n is isomorphic to a product of two fields. Thus, by Lemma 3, the graph Γ
(
E
n
) is complete bipartite. Hence, diam
⁡
(
E
n
)
=
2. Therefore, by the first parts of Theorems 2, 5, and 6, we only need to show that if n
>
1 is a type 3 integer, then diam
⁡
(
Γ
(
E
n
)
)
=
3. If n is such an integer, then there exist two commutative rings R
1 and R
2 with identities such that R
1 contains a nonzero zero divisor and E
n
=
R
1
×
R
2. Therefore, by Lemma 4, diam
⁡
(
Γ
(
E
n
)
)
=
3.Lemma 8.
LetR be a product of at least three commutative rings with identities. Then g
(
Γ
(
R
)
)
=
3.Proof.
Letx
=
(
1,0
,
…
,
0
)
,
y
=
(
0,1
,
…
,
0
) and z
=
(
0,0
,
1
,
…
). Then x, y, and z are zero divisors in this product. Moreover, x
-
-
-
y
-
-
-
z
-
-
-
x is a cycle of length 3.Theorem 9.
Letn
>
1. Then(i)
g
(
Γ
(
E
n
)
)
=
3 in each of the following cases:
(1)
n is not a square free integer; that is, n is divisible by the square of a prime;
(2)
n has at least 3 distinct prime divisors;
(3)
n is a product of two primes, with at least one of them congruent to 1 modulo 3.
(ii)
g
(
Γ
(
E
n
)
)
=
4 if n is a prime that is congruent to 1 modulo 3 or a product of two distinct primes congruent to 2 modulo 3 or n is 3 times a prime congruent to 2 modulo 3.Proof.
Letn
>
1.
(i) (1) Ifn is divisible by the square of a prime s, then n
/
s
ω
-
-
-
s
-
-
-
n
/
s
-
-
-
n
/
s
ω is a cycle of length 3.
(2) In this case,E
n can be written as a product of at least three commutative rings with identity. Thus, by Lemma 8, g
(
Γ
(
E
n
)
)
=
3.
(3) Letn
=
q
s, where q is a prime congruent to 1 modulo 3. If q
=
s, then this case is treated in the second part of Theorem 5. If q
≠
s, then E
n
≅
E
q
×
E
s. There exist integers a and b such that q
=
(
a
+
b
ω
)
(
a
+
b
ω
¯
). The following is a cycle in Γ
(
E
q
×
E
s
) of length 3:
(
a
+
b
ω
,
0
)
-
-
-
(
a
+
b
ω
¯
,
1
)
-
-
-
(
0,1
)
-
-
-
(
a
+
b
ω
,
0
).
(ii) The casen
=
q is treated in the second part of Theorem 5. If n is a product of two distinct primes congruent to 2 modulo 3, then E
n is a product of two fields. Thus, by Lemma 3, Γ
(
E
n
) is complete bipartite. If n is 3 times a prime congruent to 2 modulo 3, then E
n
≅
E
3
×
E
p. One can easily show that Γ
(
E
3
×
E
p
) is a bipartite graph that contains a cycle. Therefore, g
(
Γ
(
E
n
)
)
=
4.


### 4.2. Characterization of Complete, Complete Bipartite, Bipartite, Regular, Eulerian, Hamiltonian, or Chordal Graphs

#### 4.2.1. When IsΓ
(
E
n
) Complete, Complete Bipartite, Bipartite, or Regular?

Theorem 10.
The graphΓ
(
E
n
) is complete if and only if n
=
3 or n
=
p
2 for some prime integer p such that p
≡
2
(
mod
⁡
3
).Proof.
Ifn
=
3, then Γ
(
E
n
)
=
K
2. If n
=
p
2, then the zero divisors of E
n are given by the principal ideal p. Thus, any two zero divisors are adjacent. Hence, the graph Γ
(
E
p
2
) is complete. Conversely, assume that the graph Γ
(
E
n
) is complete. Then diam
⁡
(
Γ
(
E
n
)
)
=
1. Thus by Theorem 9, n
=
3 or n
=
p
2 for some prime integer p such that p
≡
2
(
mod
⁡
3
).Theorem 11.
The graphΓ
(
E
n
) is complete bipartite if and only if n
=
q or n
=
p
1
p
2 for some primes q, p
1, and p
2, where q
≡
1
(
mod
⁡
3
) and p
1
,
p
2
≡
2
(
mod
⁡
3
).Proof.
Ifn
=
q or n
=
p
1
p
2, then E
n is a product of two fields, thus complete bipartite by Lemma 3. Conversely, if Γ
(
E
n
) is complete bipartite, then diam
⁡
(
Γ
(
E
n
)
)
=
2 and g
(
Γ
(
E
n
)
)
=
4. Thus by Theorem 7, n
=
3
k for some k
>
1 or n
=
p
k for some k
>
2 or n
=
q or n
=
p
1
p
2. If n
=
3
k for some k
>
1 or n
=
p
k for some k
>
2, then by Theorems 2 and 6 the girth is not 4. Hence, n
=
q or n
=
p
1
p
2.Lemma 12.
IfR is a local ring with maximal ideal M such that M
>
4, then Γ
(
R
) contains a triangle and hence cannot be bipartite.Proof.
LetM be the maximal ideal of R. If M
2
=
{
0
}, then any three nonzero elements in M form a triangle in Γ
(
R
). Assume M
n
=
{
0
} such that n
>
2. If M
n
-
1
>
2, then clearly Γ
(
R
) contains a triangle. Assume that M
n
-
1
=
2 and let a
∈
M
n
-
1
∖
{
0
}. Then, a is adjacent to every other vertex in Γ
(
R
). If there is no other adjacency, then R
≃
Z
2
×
F, where F is a field (see [4]). This contradicts the fact that R is local. Thus, there exist b
,
c
∈
M
∖
{
0
,
a
} such that {
a
,
b
,
c
} form a triangle in Γ
(
R
), and so Γ
(
R
) cannot be bipartite.Lemma 13.
IfR
=
R
1
×
R
2, where R
2 is a ring with at least two nonzero zero divisors, then Γ
(
R
) cannot be bipartite. In particular, if R is a product of more than two rings, then Γ
(
R
) cannot be bipartite.Proof.
Leta
,
b
∈
R
2
∖
{
0
} such that a
≠
b and a
b
=
0. Then the vertices (
1,0
), (
0
,
a
), and (
0
,
b
) form a triangle in Γ
(
R
). Hence Γ
(
R
) cannot be bipartite. If R is a product of more than two rings, then we may write R
=
R
1
×
R
2
×
R
3. The ring R
2
×
R
3 contains at least two nonzero zero divisors, namely, (
1,0
) and (
0,1
).Therefore, we deduce the following.Theorem 14.
The graphΓ
(
E
n
) is bipartite if and only if it is complete bipartite (if and only if n
=
q or n
=
p
1
p
2 for some primes q, p
1, and p
2, where q
≡
1
(
mod
⁡
3
) and p
1
,
p
2
≡
2
(
mod
⁡
3
)).Recall that a graph is regular if each vertex has the same number of neighbors. An example of a regular graph is the complete graph. A good question aboutΓ
(
E
n
) is, is there a graph of the form Γ
(
E
n
) that is regular and incomplete? Before we give an answer, we prove the following.Lemma 15.
If a ringR is a product of two finite integral domains that have the same number of elements, then the graph Γ
(
R
) is regular.Proof.
Assume thatR
=
D
1
×
D
2. Then, Γ
(
R
) is a complete bipartite graph by Lemma 3. So, every vertex has the same number of neighbors. Thus, Γ
(
R
) is regular.Lemma 16.
LetR
=
R
1
×
R
2, where R
1 and R
2 are commutative rings with identity and zero divisors. If (without loss of generality) the graph Γ
(
R
1
) is not regular, then the graph Γ
(
R
) is not regular.Proof.
Since the graphΓ
(
R
1
) is not regular, the ring R
1 contains zero divisors x
1
,
x
2 with different degrees. Clearly, for i
=
1,2
,
x
i and (
x
i
,
1
) have the same degrees. Thus, (
x
1
,
1
) and (
x
2
,
1
) have different degrees. Therefore, the graph Γ
(
R
) is not regular.Theorem 17.
(1) For anyk
>
1, the graph Γ
(
E
3
k
) is not regular.
(2) For any primeq
≡
1
(
mod
⁡
3
), the graph Γ
(
E
q
2
) is not regular.
(3) For anyk
>
2 and any prime s, the graph Γ
(
E
s
k
) is not regular.
(4) Ifn is divisible by the product of two distinct primes, then the graph Γ
(
E
n
) is not regular.Proof.
(1) Ifk
>
1, then the ring E
3
k is local with the unique maximal ideal 2
+
ω. This ideal constitutes the zero divisors of E
q
k. By Corollary  2.7 in [4], there is a vertex of Γ
(
E
3
k
) that is adjacent to every other vertex. Hence, there is a vertex with 3
2
k
-
1
-
2 neighbors. The vertex 3 has 8 neighbors, namely, {
a
+
b
ω
∣
a
,
b not both equal zero and a
,
b
∈
{
0
,
3
k
-
1
,
2
×
3
k
-
1
}
}. Since k
>
1, 3
2
k
-
1
-
2
≠
8. Therefore, the graph Γ
(
E
3
k
) is not regular.
(2) Letq be a prime congruent to 1 modulo 3. Then there exist integers x
,
y such that q
=
(
x
+
y
ω
)
(
x
+
y
ω
¯
). We will see that (
x
+
y
ω
) and q have different number of neighbors. If a
+
b
ω is a neighbor of x
+
y
ω, then (
a
+
b
ω
)
(
x
+
y
ω
)
=
0 (in E
q
2). So there exists α
+
β
ω in Z
[
ω
] such that (
a
+
b
ω
)
(
x
+
y
ω
)
=
q
2
(
α
+
β
ω
)
=
q
(
x
+
y
ω
)
(
x
+
y
ω
¯
)
(
α
+
β
ω
). Since Z
[
ω
] is an integral domain, (
a
+
b
ω
)
=
q
(
x
+
y
ω
¯
)
(
α
+
β
ω
). Hence, the neighbors of x
+
y
ω are contained in the ideal q
(
x
+
y
ω
¯
). Conversely, every element in this ideal is a neighbor of x
+
y
ω. Similarly, one can show that the ideal q constitutes the neighbors of q. Since the ideals q
(
x
+
y
ω
¯
) and q are finite and q
(
x
+
y
ω
¯
) is strictly contained in q, x
+
y
ω and q have different number of neighbors.
(3) Letx
=
s
+
s
ω and y
=
s
k
-
1
+
s
k
-
1
ω. Since k
>
2, x
≠
y. Moreover, x and y are zero divisors in E
p
k because they are not units. A nonzero zero divisor a
+
b
ω is a neighbor of x
=
s
+
s
ω if and only if (
a
+
b
ω
)
(
s
+
s
ω
)
=
0 if and only if (
a
+
b
ω
)
s
(
1
+
ω
)
=
0 if and only if (
a
+
b
ω
)
s
=
0 because 1
+
ω is a unit in E
s
k. There are s choices for a and the same number of choices for b, namely, 0
,
s
k
-
1
,
2
s
k
-
1
,
…
,
(
s
-
1
)
s
k
-
1. Thus, there are s
2
-
1 neighbors of x. One can follow the same technique to show that there are s
2
k
-
2
-
1 neighbors of y
=
s
k
-
1
+
s
k
-
1
ω. Since k
>
2, s
2
k
-
2
-
1
≠
s
2
-
1; that is, the number of neighbors of x and y is different.
(4) Letr
,
s be two distinct prime divisors of n. Then x
=
n
/
r and y
=
n
/
s are two nonzero zero divisors of E
n. A zero divisor a
+
b
ω is a neighbor of x
=
n
/
r if and only if a
x and b
x are multiples of n. There are x choices for a and the same number of choices for b, namely, 0
,
r
,
2
r
,
…
,
(
x
-
1
)
r. Thus, there are x
2
-
1 neighbors of x. Similarly, there are y
2
-
1 neighbors of y. Since r
≠
s, x
2
-
1
≠
y
2
-
1; that is, the number of neighbors of x and y is different.Theorem 18.
The graphΓ
(
E
n
) is regular if and only if n
=
3 and n
=
p
2 for some prime p such that p
≡
2
(
mod
⁡
3
) or n
=
q for some prime q such that q
≡
1
(
mod
⁡
3
).Proof.
Ifn
=
3 or n
=
p
2 for some prime p such that p
≡
2
(
mod
⁡
3
), then the graph Γ
(
E
n
) is complete and hence regular. If q is a prime such that q
≡
1
(
mod
⁡
3
), then E
q is the product of two finite fields that have the same number of elements. Therefore, by Lemma 15, the graph Γ
(
E
q
) is regular. The converse follows from Lemma 16 and Theorem 17.


#### 4.2.2.  When IsΓ
(
E
n
) Eulerian, Hamiltonian, or Chordal?

A graphΓ is called Eulerian if there exists a closed trail containing every edge of Γ. We now characterize n for which the graph Γ
(
E
n
) is Eulerian. We will do this in two steps.Step 1 (whenE
n is local).
It is shown in [1] that E
n is a local ring if and only if n
=
3 or n
=
p
k, where k
>
1 and p is a prime integer such that p
≡
2
(
mod
⁡
3
). In this case E
n
=
n
2. Also it is shown in [13] that, for a finite local ring R with a maximal ideal M, the graph Γ
(
R
) is Eulerian if and only if R is even and x
2
=
0 for each x
∈
M. Hence, we have the following result.Theorem 19.
IfE
n is local, then Γ
(
E
n
) is Eulerian if and only if n
=
4.Step 2 (whenE
n is nonlocal).
Ifn
=
3
k
∏
i
=
1
m
p
i
m
i
q
i
n
i where p
i and q
i are prime integers such that p
i
≡
2
(
mod
⁡
3
) and q
i
≡
1
(
mod
⁡
3
), then E
n
≃
E
3
k
×
∏
i
=
1
m
E
p
i
m
i
×
∏
i
=
1
m
E
q
i
n
i. Moreover, E
q
i
n
i
≃
E
/
(
x
i
+
y
i
ω
¯
)
q
i
n
i
×
E
/
(
x
i
+
y
i
ω
)
q
i
n
i, where x
i and y
i are integers such that q
i
=
(
x
i
+
y
i
ω
¯
)
(
x
i
+
y
i
ω
). It is shown in [13] that, for a finite nonlocal ring R, the graph Γ
(
R
) is Eulerian if and only if R is a direct product of fields, each of which is of odd order. See also the result of Akbari and Mohammadian (Proposition  1 in [6]). Thus we have the following theorem.Theorem 20.
IfE
n is nonlocal, then Γ
(
E
n
) is Eulerian if and only if n is a prime integer such that n
≡
1
(
mod
⁡
3
) or n is a square free composite integer not divisible by 2 nor 3.Combining the two theorems gives the following.Theorem 21.
The graphΓ
(
E
n
) is Eulerian if and only if n
=
4 or n is a prime integer such that n
≡
1
(
mod
⁡
3
) or n is a square free composite integer not divisible by 2 nor 3.We now characterizen for which Γ
(
E
n
) is Hamiltonian. Recall that a Hamiltonian cycle of a graph Γ is a cycle that contains every vertex of Γ. A graph is Hamiltonian if it contains a Hamiltonian cycle. It is shown in [5] that, for a finite principal ideal ring R, if Γ
(
R
) is Hamiltonian, then it is either a complete graph or a complete bipartite graph.Note that a complete bipartite graph with two parts of different orders cannot be Hamiltonian. Thus we have the following result.Theorem 22.
The graphΓ
(
E
n
) is Hamiltonian if and only if n
=
p
2 or n
=
q for some prime integers q and p, where q
≡
1
(
mod
⁡
3
) and p
≡
2
(
mod
⁡
3
).We conclude this paper by characterizingn for which Γ
(
E
n
) is a chordal graph. Recall that a graph is chordal if it has no induced cycle of length greater than 3.Lemma 23.
IfR is a local principal ideal ring, then Γ
(
R
) is chordal.Proof.
LetM be the maximal ideal of R and let a
∈
R such that M
=
a. Any element in M can be written in the form u
a
m, where m
∈
N and u is a unit in R. Since R is finite, there exists n
∈
N such that a
n
=
0. Assume that u
1
a
n
1
-
-
-
u
2
a
n
2
-
-
-
u
3
a
n
3
-
-
-
u
4
a
n
4 is a path in a cycle in Γ
(
R
). Then n
1
+
n
2
≥
n, n
2
+
n
3
≥
n and n
3
+
n
4
≥
n, and so n
1
+
n
2
+
n
3
+
n
4
≥
2
n, which implies that n
1
+
n
3
≥
n or n
2
+
n
4
≥
n. Thus, there is a chord in Γ
(
R
) joining (u
1
a
n
1 and u
3
a
n
3) or (u
2
a
n
2 and u
4
a
n
4).Lemma 24.
IfR
=
R
1
×
R
2 with R
j
>
2 for j
=
1,2, then Γ
(
R
) is not chordal.Proof.
Leta
∈
R
1
∖
{
1,0
} and b
∈
R
2
∖
{
1,0
}. Then, (
1,0
)
-
-
-
(
0
,
b
)
-
-
-
(
a
,
0
)
-
-
-
(
0,1
)
-
-
-
(
1,0
) is an induced cycle in Γ
(
R
) with no chords.Therefore, we deduce the following.Theorem 25.
The graphΓ
(
E
n
) is chordal if and only if E
n is local (if and only if n
=
3
n or p
m with n
≥
1 and m
>
1).


## 4.1. Diameter and Girth

Theorem 7.
diam
⁡
(
Γ
(
E
n
)
) equals 1 if and only if n
=
3 or n
=
p
2 and equals 2 if and only if n
=
3
k for some k
>
1, n
=
p
k for some k
>
2, n
=
q, or n
=
p
1
p
2. Otherwise diam
⁡
(
Γ
(
E
n
)
) equals 3.Proof.
Let us say that a positive integern
>
1 is of type 1 if n
=
3 or n
=
p
2, type 2 if n
=
3
k for some k
>
1 or n
=
p
k for some k
>
2 or n
=
q or n
=
p
1
p
2, and type 3 otherwise. If n
=
p
1
p
2, then E
n is isomorphic to a product of two fields. Thus, by Lemma 3, the graph Γ
(
E
n
) is complete bipartite. Hence, diam
⁡
(
E
n
)
=
2. Therefore, by the first parts of Theorems 2, 5, and 6, we only need to show that if n
>
1 is a type 3 integer, then diam
⁡
(
Γ
(
E
n
)
)
=
3. If n is such an integer, then there exist two commutative rings R
1 and R
2 with identities such that R
1 contains a nonzero zero divisor and E
n
=
R
1
×
R
2. Therefore, by Lemma 4, diam
⁡
(
Γ
(
E
n
)
)
=
3.Lemma 8.
LetR be a product of at least three commutative rings with identities. Then g
(
Γ
(
R
)
)
=
3.Proof.
Letx
=
(
1,0
,
…
,
0
)
,
y
=
(
0,1
,
…
,
0
) and z
=
(
0,0
,
1
,
…
). Then x, y, and z are zero divisors in this product. Moreover, x
-
-
-
y
-
-
-
z
-
-
-
x is a cycle of length 3.Theorem 9.
Letn
>
1. Then(i)
g
(
Γ
(
E
n
)
)
=
3 in each of the following cases:
(1)
n is not a square free integer; that is, n is divisible by the square of a prime;
(2)
n has at least 3 distinct prime divisors;
(3)
n is a product of two primes, with at least one of them congruent to 1 modulo 3.
(ii)
g
(
Γ
(
E
n
)
)
=
4 if n is a prime that is congruent to 1 modulo 3 or a product of two distinct primes congruent to 2 modulo 3 or n is 3 times a prime congruent to 2 modulo 3.Proof.
Letn
>
1.
(i) (1) Ifn is divisible by the square of a prime s, then n
/
s
ω
-
-
-
s
-
-
-
n
/
s
-
-
-
n
/
s
ω is a cycle of length 3.
(2) In this case,E
n can be written as a product of at least three commutative rings with identity. Thus, by Lemma 8, g
(
Γ
(
E
n
)
)
=
3.
(3) Letn
=
q
s, where q is a prime congruent to 1 modulo 3. If q
=
s, then this case is treated in the second part of Theorem 5. If q
≠
s, then E
n
≅
E
q
×
E
s. There exist integers a and b such that q
=
(
a
+
b
ω
)
(
a
+
b
ω
¯
). The following is a cycle in Γ
(
E
q
×
E
s
) of length 3:
(
a
+
b
ω
,
0
)
-
-
-
(
a
+
b
ω
¯
,
1
)
-
-
-
(
0,1
)
-
-
-
(
a
+
b
ω
,
0
).
(ii) The casen
=
q is treated in the second part of Theorem 5. If n is a product of two distinct primes congruent to 2 modulo 3, then E
n is a product of two fields. Thus, by Lemma 3, Γ
(
E
n
) is complete bipartite. If n is 3 times a prime congruent to 2 modulo 3, then E
n
≅
E
3
×
E
p. One can easily show that Γ
(
E
3
×
E
p
) is a bipartite graph that contains a cycle. Therefore, g
(
Γ
(
E
n
)
)
=
4.


## 4.2. Characterization of Complete, Complete Bipartite, Bipartite, Regular, Eulerian, Hamiltonian, or Chordal Graphs

### 4.2.1. When IsΓ
(
E
n
) Complete, Complete Bipartite, Bipartite, or Regular?

Theorem 10.
The graphΓ
(
E
n
) is complete if and only if n
=
3 or n
=
p
2 for some prime integer p such that p
≡
2
(
mod
⁡
3
).Proof.
Ifn
=
3, then Γ
(
E
n
)
=
K
2. If n
=
p
2, then the zero divisors of E
n are given by the principal ideal p. Thus, any two zero divisors are adjacent. Hence, the graph Γ
(
E
p
2
) is complete. Conversely, assume that the graph Γ
(
E
n
) is complete. Then diam
⁡
(
Γ
(
E
n
)
)
=
1. Thus by Theorem 9, n
=
3 or n
=
p
2 for some prime integer p such that p
≡
2
(
mod
⁡
3
).Theorem 11.
The graphΓ
(
E
n
) is complete bipartite if and only if n
=
q or n
=
p
1
p
2 for some primes q, p
1, and p
2, where q
≡
1
(
mod
⁡
3
) and p
1
,
p
2
≡
2
(
mod
⁡
3
).Proof.
Ifn
=
q or n
=
p
1
p
2, then E
n is a product of two fields, thus complete bipartite by Lemma 3. Conversely, if Γ
(
E
n
) is complete bipartite, then diam
⁡
(
Γ
(
E
n
)
)
=
2 and g
(
Γ
(
E
n
)
)
=
4. Thus by Theorem 7, n
=
3
k for some k
>
1 or n
=
p
k for some k
>
2 or n
=
q or n
=
p
1
p
2. If n
=
3
k for some k
>
1 or n
=
p
k for some k
>
2, then by Theorems 2 and 6 the girth is not 4. Hence, n
=
q or n
=
p
1
p
2.Lemma 12.
IfR is a local ring with maximal ideal M such that M
>
4, then Γ
(
R
) contains a triangle and hence cannot be bipartite.Proof.
LetM be the maximal ideal of R. If M
2
=
{
0
}, then any three nonzero elements in M form a triangle in Γ
(
R
). Assume M
n
=
{
0
} such that n
>
2. If M
n
-
1
>
2, then clearly Γ
(
R
) contains a triangle. Assume that M
n
-
1
=
2 and let a
∈
M
n
-
1
∖
{
0
}. Then, a is adjacent to every other vertex in Γ
(
R
). If there is no other adjacency, then R
≃
Z
2
×
F, where F is a field (see [4]). This contradicts the fact that R is local. Thus, there exist b
,
c
∈
M
∖
{
0
,
a
} such that {
a
,
b
,
c
} form a triangle in Γ
(
R
), and so Γ
(
R
) cannot be bipartite.Lemma 13.
IfR
=
R
1
×
R
2, where R
2 is a ring with at least two nonzero zero divisors, then Γ
(
R
) cannot be bipartite. In particular, if R is a product of more than two rings, then Γ
(
R
) cannot be bipartite.Proof.
Leta
,
b
∈
R
2
∖
{
0
} such that a
≠
b and a
b
=
0. Then the vertices (
1,0
), (
0
,
a
), and (
0
,
b
) form a triangle in Γ
(
R
). Hence Γ
(
R
) cannot be bipartite. If R is a product of more than two rings, then we may write R
=
R
1
×
R
2
×
R
3. The ring R
2
×
R
3 contains at least two nonzero zero divisors, namely, (
1,0
) and (
0,1
).Therefore, we deduce the following.Theorem 14.
The graphΓ
(
E
n
) is bipartite if and only if it is complete bipartite (if and only if n
=
q or n
=
p
1
p
2 for some primes q, p
1, and p
2, where q
≡
1
(
mod
⁡
3
) and p
1
,
p
2
≡
2
(
mod
⁡
3
)).Recall that a graph is regular if each vertex has the same number of neighbors. An example of a regular graph is the complete graph. A good question aboutΓ
(
E
n
) is, is there a graph of the form Γ
(
E
n
) that is regular and incomplete? Before we give an answer, we prove the following.Lemma 15.
If a ringR is a product of two finite integral domains that have the same number of elements, then the graph Γ
(
R
) is regular.Proof.
Assume thatR
=
D
1
×
D
2. Then, Γ
(
R
) is a complete bipartite graph by Lemma 3. So, every vertex has the same number of neighbors. Thus, Γ
(
R
) is regular.Lemma 16.
LetR
=
R
1
×
R
2, where R
1 and R
2 are commutative rings with identity and zero divisors. If (without loss of generality) the graph Γ
(
R
1
) is not regular, then the graph Γ
(
R
) is not regular.Proof.
Since the graphΓ
(
R
1
) is not regular, the ring R
1 contains zero divisors x
1
,
x
2 with different degrees. Clearly, for i
=
1,2
,
x
i and (
x
i
,
1
) have the same degrees. Thus, (
x
1
,
1
) and (
x
2
,
1
) have different degrees. Therefore, the graph Γ
(
R
) is not regular.Theorem 17.
(1) For anyk
>
1, the graph Γ
(
E
3
k
) is not regular.
(2) For any primeq
≡
1
(
mod
⁡
3
), the graph Γ
(
E
q
2
) is not regular.
(3) For anyk
>
2 and any prime s, the graph Γ
(
E
s
k
) is not regular.
(4) Ifn is divisible by the product of two distinct primes, then the graph Γ
(
E
n
) is not regular.Proof.
(1) Ifk
>
1, then the ring E
3
k is local with the unique maximal ideal 2
+
ω. This ideal constitutes the zero divisors of E
q
k. By Corollary  2.7 in [4], there is a vertex of Γ
(
E
3
k
) that is adjacent to every other vertex. Hence, there is a vertex with 3
2
k
-
1
-
2 neighbors. The vertex 3 has 8 neighbors, namely, {
a
+
b
ω
∣
a
,
b not both equal zero and a
,
b
∈
{
0
,
3
k
-
1
,
2
×
3
k
-
1
}
}. Since k
>
1, 3
2
k
-
1
-
2
≠
8. Therefore, the graph Γ
(
E
3
k
) is not regular.
(2) Letq be a prime congruent to 1 modulo 3. Then there exist integers x
,
y such that q
=
(
x
+
y
ω
)
(
x
+
y
ω
¯
). We will see that (
x
+
y
ω
) and q have different number of neighbors. If a
+
b
ω is a neighbor of x
+
y
ω, then (
a
+
b
ω
)
(
x
+
y
ω
)
=
0 (in E
q
2). So there exists α
+
β
ω in Z
[
ω
] such that (
a
+
b
ω
)
(
x
+
y
ω
)
=
q
2
(
α
+
β
ω
)
=
q
(
x
+
y
ω
)
(
x
+
y
ω
¯
)
(
α
+
β
ω
). Since Z
[
ω
] is an integral domain, (
a
+
b
ω
)
=
q
(
x
+
y
ω
¯
)
(
α
+
β
ω
). Hence, the neighbors of x
+
y
ω are contained in the ideal q
(
x
+
y
ω
¯
). Conversely, every element in this ideal is a neighbor of x
+
y
ω. Similarly, one can show that the ideal q constitutes the neighbors of q. Since the ideals q
(
x
+
y
ω
¯
) and q are finite and q
(
x
+
y
ω
¯
) is strictly contained in q, x
+
y
ω and q have different number of neighbors.
(3) Letx
=
s
+
s
ω and y
=
s
k
-
1
+
s
k
-
1
ω. Since k
>
2, x
≠
y. Moreover, x and y are zero divisors in E
p
k because they are not units. A nonzero zero divisor a
+
b
ω is a neighbor of x
=
s
+
s
ω if and only if (
a
+
b
ω
)
(
s
+
s
ω
)
=
0 if and only if (
a
+
b
ω
)
s
(
1
+
ω
)
=
0 if and only if (
a
+
b
ω
)
s
=
0 because 1
+
ω is a unit in E
s
k. There are s choices for a and the same number of choices for b, namely, 0
,
s
k
-
1
,
2
s
k
-
1
,
…
,
(
s
-
1
)
s
k
-
1. Thus, there are s
2
-
1 neighbors of x. One can follow the same technique to show that there are s
2
k
-
2
-
1 neighbors of y
=
s
k
-
1
+
s
k
-
1
ω. Since k
>
2, s
2
k
-
2
-
1
≠
s
2
-
1; that is, the number of neighbors of x and y is different.
(4) Letr
,
s be two distinct prime divisors of n. Then x
=
n
/
r and y
=
n
/
s are two nonzero zero divisors of E
n. A zero divisor a
+
b
ω is a neighbor of x
=
n
/
r if and only if a
x and b
x are multiples of n. There are x choices for a and the same number of choices for b, namely, 0
,
r
,
2
r
,
…
,
(
x
-
1
)
r. Thus, there are x
2
-
1 neighbors of x. Similarly, there are y
2
-
1 neighbors of y. Since r
≠
s, x
2
-
1
≠
y
2
-
1; that is, the number of neighbors of x and y is different.Theorem 18.
The graphΓ
(
E
n
) is regular if and only if n
=
3 and n
=
p
2 for some prime p such that p
≡
2
(
mod
⁡
3
) or n
=
q for some prime q such that q
≡
1
(
mod
⁡
3
).Proof.
Ifn
=
3 or n
=
p
2 for some prime p such that p
≡
2
(
mod
⁡
3
), then the graph Γ
(
E
n
) is complete and hence regular. If q is a prime such that q
≡
1
(
mod
⁡
3
), then E
q is the product of two finite fields that have the same number of elements. Therefore, by Lemma 15, the graph Γ
(
E
q
) is regular. The converse follows from Lemma 16 and Theorem 17.


### 4.2.2.  When IsΓ
(
E
n
) Eulerian, Hamiltonian, or Chordal?

A graphΓ is called Eulerian if there exists a closed trail containing every edge of Γ. We now characterize n for which the graph Γ
(
E
n
) is Eulerian. We will do this in two steps.Step 1 (whenE
n is local).
It is shown in [1] that E
n is a local ring if and only if n
=
3 or n
=
p
k, where k
>
1 and p is a prime integer such that p
≡
2
(
mod
⁡
3
). In this case E
n
=
n
2. Also it is shown in [13] that, for a finite local ring R with a maximal ideal M, the graph Γ
(
R
) is Eulerian if and only if R is even and x
2
=
0 for each x
∈
M. Hence, we have the following result.Theorem 19.
IfE
n is local, then Γ
(
E
n
) is Eulerian if and only if n
=
4.Step 2 (whenE
n is nonlocal).
Ifn
=
3
k
∏
i
=
1
m
p
i
m
i
q
i
n
i where p
i and q
i are prime integers such that p
i
≡
2
(
mod
⁡
3
) and q
i
≡
1
(
mod
⁡
3
), then E
n
≃
E
3
k
×
∏
i
=
1
m
E
p
i
m
i
×
∏
i
=
1
m
E
q
i
n
i. Moreover, E
q
i
n
i
≃
E
/
(
x
i
+
y
i
ω
¯
)
q
i
n
i
×
E
/
(
x
i
+
y
i
ω
)
q
i
n
i, where x
i and y
i are integers such that q
i
=
(
x
i
+
y
i
ω
¯
)
(
x
i
+
y
i
ω
). It is shown in [13] that, for a finite nonlocal ring R, the graph Γ
(
R
) is Eulerian if and only if R is a direct product of fields, each of which is of odd order. See also the result of Akbari and Mohammadian (Proposition  1 in [6]). Thus we have the following theorem.Theorem 20.
IfE
n is nonlocal, then Γ
(
E
n
) is Eulerian if and only if n is a prime integer such that n
≡
1
(
mod
⁡
3
) or n is a square free composite integer not divisible by 2 nor 3.Combining the two theorems gives the following.Theorem 21.
The graphΓ
(
E
n
) is Eulerian if and only if n
=
4 or n is a prime integer such that n
≡
1
(
mod
⁡
3
) or n is a square free composite integer not divisible by 2 nor 3.We now characterizen for which Γ
(
E
n
) is Hamiltonian. Recall that a Hamiltonian cycle of a graph Γ is a cycle that contains every vertex of Γ. A graph is Hamiltonian if it contains a Hamiltonian cycle. It is shown in [5] that, for a finite principal ideal ring R, if Γ
(
R
) is Hamiltonian, then it is either a complete graph or a complete bipartite graph.Note that a complete bipartite graph with two parts of different orders cannot be Hamiltonian. Thus we have the following result.Theorem 22.
The graphΓ
(
E
n
) is Hamiltonian if and only if n
=
p
2 or n
=
q for some prime integers q and p, where q
≡
1
(
mod
⁡
3
) and p
≡
2
(
mod
⁡
3
).We conclude this paper by characterizingn for which Γ
(
E
n
) is a chordal graph. Recall that a graph is chordal if it has no induced cycle of length greater than 3.Lemma 23.
IfR is a local principal ideal ring, then Γ
(
R
) is chordal.Proof.
LetM be the maximal ideal of R and let a
∈
R such that M
=
a. Any element in M can be written in the form u
a
m, where m
∈
N and u is a unit in R. Since R is finite, there exists n
∈
N such that a
n
=
0. Assume that u
1
a
n
1
-
-
-
u
2
a
n
2
-
-
-
u
3
a
n
3
-
-
-
u
4
a
n
4 is a path in a cycle in Γ
(
R
). Then n
1
+
n
2
≥
n, n
2
+
n
3
≥
n and n
3
+
n
4
≥
n, and so n
1
+
n
2
+
n
3
+
n
4
≥
2
n, which implies that n
1
+
n
3
≥
n or n
2
+
n
4
≥
n. Thus, there is a chord in Γ
(
R
) joining (u
1
a
n
1 and u
3
a
n
3) or (u
2
a
n
2 and u
4
a
n
4).Lemma 24.
IfR
=
R
1
×
R
2 with R
j
>
2 for j
=
1,2, then Γ
(
R
) is not chordal.Proof.
Leta
∈
R
1
∖
{
1,0
} and b
∈
R
2
∖
{
1,0
}. Then, (
1,0
)
-
-
-
(
0
,
b
)
-
-
-
(
a
,
0
)
-
-
-
(
0,1
)
-
-
-
(
1,0
) is an induced cycle in Γ
(
R
) with no chords.Therefore, we deduce the following.Theorem 25.
The graphΓ
(
E
n
) is chordal if and only if E
n is local (if and only if n
=
3
n or p
m with n
≥
1 and m
>
1).


## 4.2.1. When IsΓ
(
E
n
) Complete, Complete Bipartite, Bipartite, or Regular?

Theorem 10.
The graphΓ
(
E
n
) is complete if and only if n
=
3 or n
=
p
2 for some prime integer p such that p
≡
2
(
mod
⁡
3
).Proof.
Ifn
=
3, then Γ
(
E
n
)
=
K
2. If n
=
p
2, then the zero divisors of E
n are given by the principal ideal p. Thus, any two zero divisors are adjacent. Hence, the graph Γ
(
E
p
2
) is complete. Conversely, assume that the graph Γ
(
E
n
) is complete. Then diam
⁡
(
Γ
(
E
n
)
)
=
1. Thus by Theorem 9, n
=
3 or n
=
p
2 for some prime integer p such that p
≡
2
(
mod
⁡
3
).Theorem 11.
The graphΓ
(
E
n
) is complete bipartite if and only if n
=
q or n
=
p
1
p
2 for some primes q, p
1, and p
2, where q
≡
1
(
mod
⁡
3
) and p
1
,
p
2
≡
2
(
mod
⁡
3
).Proof.
Ifn
=
q or n
=
p
1
p
2, then E
n is a product of two fields, thus complete bipartite by Lemma 3. Conversely, if Γ
(
E
n
) is complete bipartite, then diam
⁡
(
Γ
(
E
n
)
)
=
2 and g
(
Γ
(
E
n
)
)
=
4. Thus by Theorem 7, n
=
3
k for some k
>
1 or n
=
p
k for some k
>
2 or n
=
q or n
=
p
1
p
2. If n
=
3
k for some k
>
1 or n
=
p
k for some k
>
2, then by Theorems 2 and 6 the girth is not 4. Hence, n
=
q or n
=
p
1
p
2.Lemma 12.
IfR is a local ring with maximal ideal M such that M
>
4, then Γ
(
R
) contains a triangle and hence cannot be bipartite.Proof.
LetM be the maximal ideal of R. If M
2
=
{
0
}, then any three nonzero elements in M form a triangle in Γ
(
R
). Assume M
n
=
{
0
} such that n
>
2. If M
n
-
1
>
2, then clearly Γ
(
R
) contains a triangle. Assume that M
n
-
1
=
2 and let a
∈
M
n
-
1
∖
{
0
}. Then, a is adjacent to every other vertex in Γ
(
R
). If there is no other adjacency, then R
≃
Z
2
×
F, where F is a field (see [4]). This contradicts the fact that R is local. Thus, there exist b
,
c
∈
M
∖
{
0
,
a
} such that {
a
,
b
,
c
} form a triangle in Γ
(
R
), and so Γ
(
R
) cannot be bipartite.Lemma 13.
IfR
=
R
1
×
R
2, where R
2 is a ring with at least two nonzero zero divisors, then Γ
(
R
) cannot be bipartite. In particular, if R is a product of more than two rings, then Γ
(
R
) cannot be bipartite.Proof.
Leta
,
b
∈
R
2
∖
{
0
} such that a
≠
b and a
b
=
0. Then the vertices (
1,0
), (
0
,
a
), and (
0
,
b
) form a triangle in Γ
(
R
). Hence Γ
(
R
) cannot be bipartite. If R is a product of more than two rings, then we may write R
=
R
1
×
R
2
×
R
3. The ring R
2
×
R
3 contains at least two nonzero zero divisors, namely, (
1,0
) and (
0,1
).Therefore, we deduce the following.Theorem 14.
The graphΓ
(
E
n
) is bipartite if and only if it is complete bipartite (if and only if n
=
q or n
=
p
1
p
2 for some primes q, p
1, and p
2, where q
≡
1
(
mod
⁡
3
) and p
1
,
p
2
≡
2
(
mod
⁡
3
)).Recall that a graph is regular if each vertex has the same number of neighbors. An example of a regular graph is the complete graph. A good question aboutΓ
(
E
n
) is, is there a graph of the form Γ
(
E
n
) that is regular and incomplete? Before we give an answer, we prove the following.Lemma 15.
If a ringR is a product of two finite integral domains that have the same number of elements, then the graph Γ
(
R
) is regular.Proof.
Assume thatR
=
D
1
×
D
2. Then, Γ
(
R
) is a complete bipartite graph by Lemma 3. So, every vertex has the same number of neighbors. Thus, Γ
(
R
) is regular.Lemma 16.
LetR
=
R
1
×
R
2, where R
1 and R
2 are commutative rings with identity and zero divisors. If (without loss of generality) the graph Γ
(
R
1
) is not regular, then the graph Γ
(
R
) is not regular.Proof.
Since the graphΓ
(
R
1
) is not regular, the ring R
1 contains zero divisors x
1
,
x
2 with different degrees. Clearly, for i
=
1,2
,
x
i and (
x
i
,
1
) have the same degrees. Thus, (
x
1
,
1
) and (
x
2
,
1
) have different degrees. Therefore, the graph Γ
(
R
) is not regular.Theorem 17.
(1) For anyk
>
1, the graph Γ
(
E
3
k
) is not regular.
(2) For any primeq
≡
1
(
mod
⁡
3
), the graph Γ
(
E
q
2
) is not regular.
(3) For anyk
>
2 and any prime s, the graph Γ
(
E
s
k
) is not regular.
(4) Ifn is divisible by the product of two distinct primes, then the graph Γ
(
E
n
) is not regular.Proof.
(1) Ifk
>
1, then the ring E
3
k is local with the unique maximal ideal 2
+
ω. This ideal constitutes the zero divisors of E
q
k. By Corollary  2.7 in [4], there is a vertex of Γ
(
E
3
k
) that is adjacent to every other vertex. Hence, there is a vertex with 3
2
k
-
1
-
2 neighbors. The vertex 3 has 8 neighbors, namely, {
a
+
b
ω
∣
a
,
b not both equal zero and a
,
b
∈
{
0
,
3
k
-
1
,
2
×
3
k
-
1
}
}. Since k
>
1, 3
2
k
-
1
-
2
≠
8. Therefore, the graph Γ
(
E
3
k
) is not regular.
(2) Letq be a prime congruent to 1 modulo 3. Then there exist integers x
,
y such that q
=
(
x
+
y
ω
)
(
x
+
y
ω
¯
). We will see that (
x
+
y
ω
) and q have different number of neighbors. If a
+
b
ω is a neighbor of x
+
y
ω, then (
a
+
b
ω
)
(
x
+
y
ω
)
=
0 (in E
q
2). So there exists α
+
β
ω in Z
[
ω
] such that (
a
+
b
ω
)
(
x
+
y
ω
)
=
q
2
(
α
+
β
ω
)
=
q
(
x
+
y
ω
)
(
x
+
y
ω
¯
)
(
α
+
β
ω
). Since Z
[
ω
] is an integral domain, (
a
+
b
ω
)
=
q
(
x
+
y
ω
¯
)
(
α
+
β
ω
). Hence, the neighbors of x
+
y
ω are contained in the ideal q
(
x
+
y
ω
¯
). Conversely, every element in this ideal is a neighbor of x
+
y
ω. Similarly, one can show that the ideal q constitutes the neighbors of q. Since the ideals q
(
x
+
y
ω
¯
) and q are finite and q
(
x
+
y
ω
¯
) is strictly contained in q, x
+
y
ω and q have different number of neighbors.
(3) Letx
=
s
+
s
ω and y
=
s
k
-
1
+
s
k
-
1
ω. Since k
>
2, x
≠
y. Moreover, x and y are zero divisors in E
p
k because they are not units. A nonzero zero divisor a
+
b
ω is a neighbor of x
=
s
+
s
ω if and only if (
a
+
b
ω
)
(
s
+
s
ω
)
=
0 if and only if (
a
+
b
ω
)
s
(
1
+
ω
)
=
0 if and only if (
a
+
b
ω
)
s
=
0 because 1
+
ω is a unit in E
s
k. There are s choices for a and the same number of choices for b, namely, 0
,
s
k
-
1
,
2
s
k
-
1
,
…
,
(
s
-
1
)
s
k
-
1. Thus, there are s
2
-
1 neighbors of x. One can follow the same technique to show that there are s
2
k
-
2
-
1 neighbors of y
=
s
k
-
1
+
s
k
-
1
ω. Since k
>
2, s
2
k
-
2
-
1
≠
s
2
-
1; that is, the number of neighbors of x and y is different.
(4) Letr
,
s be two distinct prime divisors of n. Then x
=
n
/
r and y
=
n
/
s are two nonzero zero divisors of E
n. A zero divisor a
+
b
ω is a neighbor of x
=
n
/
r if and only if a
x and b
x are multiples of n. There are x choices for a and the same number of choices for b, namely, 0
,
r
,
2
r
,
…
,
(
x
-
1
)
r. Thus, there are x
2
-
1 neighbors of x. Similarly, there are y
2
-
1 neighbors of y. Since r
≠
s, x
2
-
1
≠
y
2
-
1; that is, the number of neighbors of x and y is different.Theorem 18.
The graphΓ
(
E
n
) is regular if and only if n
=
3 and n
=
p
2 for some prime p such that p
≡
2
(
mod
⁡
3
) or n
=
q for some prime q such that q
≡
1
(
mod
⁡
3
).Proof.
Ifn
=
3 or n
=
p
2 for some prime p such that p
≡
2
(
mod
⁡
3
), then the graph Γ
(
E
n
) is complete and hence regular. If q is a prime such that q
≡
1
(
mod
⁡
3
), then E
q is the product of two finite fields that have the same number of elements. Therefore, by Lemma 15, the graph Γ
(
E
q
) is regular. The converse follows from Lemma 16 and Theorem 17.


## 4.2.2.  When IsΓ
(
E
n
) Eulerian, Hamiltonian, or Chordal?

A graphΓ is called Eulerian if there exists a closed trail containing every edge of Γ. We now characterize n for which the graph Γ
(
E
n
) is Eulerian. We will do this in two steps.Step 1 (whenE
n is local).
It is shown in [1] that E
n is a local ring if and only if n
=
3 or n
=
p
k, where k
>
1 and p is a prime integer such that p
≡
2
(
mod
⁡
3
). In this case E
n
=
n
2. Also it is shown in [13] that, for a finite local ring R with a maximal ideal M, the graph Γ
(
R
) is Eulerian if and only if R is even and x
2
=
0 for each x
∈
M. Hence, we have the following result.Theorem 19.
IfE
n is local, then Γ
(
E
n
) is Eulerian if and only if n
=
4.Step 2 (whenE
n is nonlocal).
Ifn
=
3
k
∏
i
=
1
m
p
i
m
i
q
i
n
i where p
i and q
i are prime integers such that p
i
≡
2
(
mod
⁡
3
) and q
i
≡
1
(
mod
⁡
3
), then E
n
≃
E
3
k
×
∏
i
=
1
m
E
p
i
m
i
×
∏
i
=
1
m
E
q
i
n
i. Moreover, E
q
i
n
i
≃
E
/
(
x
i
+
y
i
ω
¯
)
q
i
n
i
×
E
/
(
x
i
+
y
i
ω
)
q
i
n
i, where x
i and y
i are integers such that q
i
=
(
x
i
+
y
i
ω
¯
)
(
x
i
+
y
i
ω
). It is shown in [13] that, for a finite nonlocal ring R, the graph Γ
(
R
) is Eulerian if and only if R is a direct product of fields, each of which is of odd order. See also the result of Akbari and Mohammadian (Proposition  1 in [6]). Thus we have the following theorem.Theorem 20.
IfE
n is nonlocal, then Γ
(
E
n
) is Eulerian if and only if n is a prime integer such that n
≡
1
(
mod
⁡
3
) or n is a square free composite integer not divisible by 2 nor 3.Combining the two theorems gives the following.Theorem 21.
The graphΓ
(
E
n
) is Eulerian if and only if n
=
4 or n is a prime integer such that n
≡
1
(
mod
⁡
3
) or n is a square free composite integer not divisible by 2 nor 3.We now characterizen for which Γ
(
E
n
) is Hamiltonian. Recall that a Hamiltonian cycle of a graph Γ is a cycle that contains every vertex of Γ. A graph is Hamiltonian if it contains a Hamiltonian cycle. It is shown in [5] that, for a finite principal ideal ring R, if Γ
(
R
) is Hamiltonian, then it is either a complete graph or a complete bipartite graph.Note that a complete bipartite graph with two parts of different orders cannot be Hamiltonian. Thus we have the following result.Theorem 22.
The graphΓ
(
E
n
) is Hamiltonian if and only if n
=
p
2 or n
=
q for some prime integers q and p, where q
≡
1
(
mod
⁡
3
) and p
≡
2
(
mod
⁡
3
).We conclude this paper by characterizingn for which Γ
(
E
n
) is a chordal graph. Recall that a graph is chordal if it has no induced cycle of length greater than 3.Lemma 23.
IfR is a local principal ideal ring, then Γ
(
R
) is chordal.Proof.
LetM be the maximal ideal of R and let a
∈
R such that M
=
a. Any element in M can be written in the form u
a
m, where m
∈
N and u is a unit in R. Since R is finite, there exists n
∈
N such that a
n
=
0. Assume that u
1
a
n
1
-
-
-
u
2
a
n
2
-
-
-
u
3
a
n
3
-
-
-
u
4
a
n
4 is a path in a cycle in Γ
(
R
). Then n
1
+
n
2
≥
n, n
2
+
n
3
≥
n and n
3
+
n
4
≥
n, and so n
1
+
n
2
+
n
3
+
n
4
≥
2
n, which implies that n
1
+
n
3
≥
n or n
2
+
n
4
≥
n. Thus, there is a chord in Γ
(
R
) joining (u
1
a
n
1 and u
3
a
n
3) or (u
2
a
n
2 and u
4
a
n
4).Lemma 24.
IfR
=
R
1
×
R
2 with R
j
>
2 for j
=
1,2, then Γ
(
R
) is not chordal.Proof.
Leta
∈
R
1
∖
{
1,0
} and b
∈
R
2
∖
{
1,0
}. Then, (
1,0
)
-
-
-
(
0
,
b
)
-
-
-
(
a
,
0
)
-
-
-
(
0,1
)
-
-
-
(
1,0
) is an induced cycle in Γ
(
R
) with no chords.Therefore, we deduce the following.Theorem 25.
The graphΓ
(
E
n
) is chordal if and only if E
n is local (if and only if n
=
3
n or p
m with n
≥
1 and m
>
1).



---

*Source: 146873-2014-12-15.xml*