arXiv:1703.01150v1 [] 3 Mar 2017

On the intersection graph of ideals of Zm

∗

S. Khojasteh

Department of Mathematics, Lahijan Branch, Islamic Azad University, Lahijan, Iran

Abstract
Let m > 1 be an integer, and let I(Zm )∗ be the set of all non-zero proper ideals of
Zm . The intersection graph of ideals of Zm , denoted by G(Zm ), is a graph with vertices
I(Zm )∗ and two distinct vertices I, J ∈ I(Zm )∗ are adjacent if and only if I ∩ J 6= 0.
Let n > 1 be an integer and Zn be a Zm -module. In this paper, we introduce and
study a kind of graph structure of Zm , denoted by Gn (Zm ). It is the undirected graph
with the vertex set I(Zm )∗ , and two distinct vertices I and J are adjacent if and only
if IZn ∩ JZn 6= 0. Clearly, Gm (Zm ) = G(Zm ). We obtain some graph theoretical
properties of Gn (Zm ) and we compute some of its numerical invariants, namely girth,
independence number, domination number, maximum degree and chromatic index.
We also determine all integer numbers n and m for which Gn (Zm ) is Eulerian.

1

Introduction

Let R be a commutative ring, and I(R)∗ be the set of all non-zero proper ideals of R.
There are many papers on assigning a graph to a ring R, for instance see [1], [2], [5] and
[6]. Also the intersection graphs of some algebraic structures such as groups, rings and
modules have been studied by several authors, see [3, 9, 10]. In [9], the intersection graph
of ideals of R, denoted by G(R), was introduced as the graph with vertices I(R)∗ and for
distinct I, J ∈ I(R)∗ , the vertices I and J are adjacent if and only if I ∩ J 6= 0. Also
in [3], the intersection graph of submodules of an R-module M , denoted by G(M ), is
defined to be the graph whose vertices are the non-zero proper submodules of M and two
∗

Key words: intersection graph, independent set, dominating set, chromatic index, Eulerian graph.
2010 Mathematics Subject Classification: 05C15, 05C25, 05C45, 05C69.
E-mail addresses: s khojasteh@liau.ac.ir (S. Khojasteh).

1

distinct vertices are adjacent if and only if they have non-zero intersection. Let n, m > 1
be integers and Zn be a Zm -module. In this paper, we associate a graph to Zm , in which
the vertex set is being the set of all non-zero proper ideals of Zm , and two distinct vertices
I and J are adjacent if and only if IZn ∩ JZn 6= 0. We denote this graph by Gn (Zm ).
Clearly, if n = m, then Gn (Zm ) is exactly the same as the intersection graph of ideals of
Zm . This implies that Gn (Zm ) is a generalization of G(Zm ). As usual, Zm denotes the
integers modulo m.
Now, we recall some definitions and notations on graphs. Let G be a graph with the
vertex set V (G) and the edge set E(G). Then we say the order of G is |V (G)| and the
size of G is |E(G)|. Suppose that x, y ∈ V (G). If x and y are adjacent, then we write x
— y. We denote by deg(x) the degree of a vertex x in G. Also, we denote the maximum
degree of G by ∆(G). We recall that a path between x and y is a sequence x = v0 —
v1 — · · · — vk = y of vertices of G such that for every i with 1 ≤ i ≤ k, the vertices
vi−1 and vi are adjacent and vi 6= vj , where i 6= j. We say that G is connected if there
is a path between any two distinct vertices of G. For vertices x and y of G, let d(x, y)
be the length of a shortest path from x to y (d(x, x) = 0 and d(x, y) = ∞ if there is
no path between x and y). The diameter of G, diam(G), is the supremum of the set
{d(x, y) : x and y are vertices of G}. The girth of G, denoted by gr(G), is the length of
a shortest cycle in G (gr(G) = ∞ if G contains no cycles). We use n-cycle to denote the
cycle with n vertices, where n ≥ 3. Also, we denote the complete graph on n vertices by
Kn . A null graph is a graph containing no edges. We use Kn to denote the null graph of
order n. The disjoint union of two vertex-disjoint graphs G1 and G2 , which is denoted by
G1 ∪ G2 , is a graph with V (G1 ∪ G2 ) = V (G1 ) ∪ V (G2 ) and E(G1 ∪ G2 ) = E(G1 ) ∪ E(G2 ).
An independent set is a subset of the vertices of a graph such that no vertices are adjacent.
The number of vertices in a maximum independent set of G is called the independence
number of G and is denoted by α(G). A dominating set is a subset S of V (G) such that
every vertex of V (G) \ S is adjacent to at least one vertex in S. The number of vertices in
a smallest dominating set denoted by γ(G), is called the domination number of G. Recall
that a k-edge coloring of G is an assignment of k colors {1, . . . , k} to the edges of G such
that no two adjacent edges have the same color, and the chromatic index of G, χ′ (G), is
the smallest integer k such that G has a k-edge coloring.
In [9], the authors were mainly interested in the study of intersection graph of ideals
of Zm . For instance, they determined the values of m for which G(Zm ) is connected,
complete, Eulerian or has a cycle. In this article, we generalize these results to Gn (Zm )
and also, we find some new results. In Section 2, we compute its girth, independence

2

number, domination number and maximum degree. We also determine all integer numbers
n and m for which Gn (Zm ) is a forest. In Section 3, we investigate the chromatic index of
Gn (Zm ). In the last section, we determine all integer numbers n and m for which Gn (Zm )
is Eulerian.

2

Basic Properties of Gn (Zm)

Let n, m > 1 be integers and Zn be a Zm -module. Clearly, Zn is a Zm -module if and
only if n divides m. Throughout the paper, without loss of generality, we assume that
m = pα1 1 · · · pαs s and n = pβ1 1 · · · pβs s , where pi ’s are distinct primes, αi ’s are positive integers,
βi ’s are non-negative integers, and 0 ≤ βi ≤ αi for i = 1, . . . , s. Let S = {1, . . . , s},
S ′ = {i ∈ S : βi 6= 0}. The cardinality of S ′ is denoted by s′ . Also, we denote the least
common multiple of integers a and b by [a, b]. We write a|b (a ∤ b) if a divides b (a does
not divide b). We begin with a simple example.
Example 1. Let m = 12. Then we have the following graphs.
2Z12

3Z12

2Z12

3Z12

2Z12

3Z12

2Z12

3Z12

4Z12

6Z12

4Z12

6Z12

4Z12

6Z12

4Z12

6Z12

G(Z12 )

G2 (Z12 )

G3 (Z12 )

G4 (Z12 )

Remark 1. It is easy to see that I(Zm ) = {dZm : d divides m} and |I(Zm )∗ | =

Qs

i=1 (αi +

1) − 2. Let Zn be a Zm -module. If n|d, then dZm is an isolated vertex of Gn (Zm ).
Obviously, d1 Zm and d2 Zm are adjacent in Gn (Zm ) if and only if n ∤ [d1 , d2 ]. This implies
that Gn (Zm ) is a subgraph of G(Zm ).
By [3, Theorem 2.5], we have gr(G(Zm )) ∈ {3, ∞}. We extend this result to Gn (Zm ).
Theorem 1. Let Zn be a Zm -module. Then gr(Gn (Zm )) ∈ {3, ∞}.
Proof. With no loss of generality assume that S ′ = {1, . . . , s′ }. Clearly, if s′ ≥ 3, then
p1 Zm — p2 Zm — p1 p2 Zm is a 3-cycle in Gn (Zm ). Therefore gr(Gn (Zm )) = 3. Now,
consider two following cases:
3

Case 1. s′ = 2. If s ≥ 3, then p1 Zm — p3 Zm — p1 p3 Zm is a 3-cycle in Gn (Zm ).
So we may assume that s = 2. If αi ≥ 3 for some i, i = 1, 2, then pi Zm — p2i Zm —
p3i Zm is a 3-cycle in Gn (Zm ). Also, if βi ≥ 2 for some i, i = 1, 2, then p1 Zm — p2 Zm —
p1 p2 Zm is a 3-cycle in Gn (Zm ). Now, assume that n = p1 p2 and α1 , α2 = 1, 2. It is easy
to see that gr(Gn (Zm )) = ∞. Note that Gp1 p2 (Zp1 p2 ) ∼
= K2 , Gp1 p2 (Zp21 p2 ) ∼
= K2 ∪ K2 , and
∼
Gp p (Z 2 2 ) = K2 ∪ K2 ∪ K3 .
p1 p2

1 2

Case 2. s′ = 1. If s ≥ 3, then p2 Zm — p3 Zm — p2 p3 Zm is a 3-cycle in Gn (Zm ). So
assume that s = 2. If β1 ≥ 2, then p1 Zm — p2 Zm — p1 p2 Zm is a 3-cycle in Gn (Zm ).
Also, if α2 ≥ 3, then p2 Zm — p22 Zm — p32 Zm is a 3-cycle in Gn (Zm ). Now, suppose that
n = p1 and m = pα1 p2 or m = pα1 p2 . Then gr(Gn (Zm )) = ∞, since Gp (Z α1 ) ∼
= K2α
1

1

2

1

p1 p2

1

β
and Gp1 (Zpα1 p2 ) ∼
= K3α1 −1 ∪ K2 . Finally, assume that n = p1 1 and m = pα1 1 . If β1 ≥ 4,
1
2

then p1 Zm — p21 Zm — p31 Zm is a 3-cycle in Gn (Zm ). It is easy to see that if β1 ≤ 3, then
gr(Gpβ1 (Zpα1 )) = ∞.
1



1

As an immediate consequence of Theorem 1, we have the following corollary.
Corollary 1. Let Zn be a Zm -module. Then Gn (Zm ) is a forest if and only if one of the
following holds:
(i) n = p1 p2 , m = pα1 1 pα2 2 and α1 , α2 ≤ 2.
(ii) n = p1 , m = pα1 1 pα2 2 and α2 ≤ 2.
(iii) n = pβ1 1 , m = pα1 1 and 1 ≤ β1 ≤ 3.
By [3, Theorem 3.4], we find that G(Zm ) is a tree if and only if G(Zm ) is a star. Now,
we have a similar result.
Corollary 2. Let Zn be a Zm -module. Then Gn (Zm ) is a tree if and only if Gn (Zm ) is
a star. In particular, Gn (Zm ) is a tree if and only if one of the following holds:
(i) n = m = p21 .
(ii) n = m = p31 .
(iii) n = p1 and m = p21 .
By Corollary 1, we can characterize the values of n and m for which Gn (Zm ) is a null
graph.

4

Let Zn be a Zm -module. Then Gn (Zm ) is a null graph if and only if one

Corollary 3.

of the following holds:
(i) n = p1 and m = pα1 1 p2 .
(ii) n = p1 and m = pα1 1 .
(iii) n = p21 and m = pα1 1 .
(iv) n = m = p1 p2 .
Throughout the rest of this paper, we use A to denote the set of all isolated vertices
of Gn (Zm ).
Lemma 1.

Let Zn be a Zm -module. If Gn (Zm ) is not a null graph, then dZm is an

isolated vertex of Gn (Zm ) if and only if n|d, except for the case n = p1 p2 , m = pα1 1 p2 and
α1 ≥ 2, in which case Gn (Zm ) = Kα1 ∪ Kα1 .
Proof. Clearly, if n|d, then dZm is an isolated vertex of Gn (Zm ). For the other side
suppose that Gn (Zm ) is not a null graph, d = pr11 · · · prss is a divisor of m and n ∤ d. Since
n ∤ d, we may assume that r1 < β1 . If s ≥ 3, then dZm is adjacent to one of pα2 2 · · · pαs s Zm
or pα3 3 · · · pαs s Zm . Now, suppose that s = 2. If r1 6= 0, then dZm and pα2 2 Zm are adjacent.
Hence r1 = 0 and d = pr22 . If r2 ≥ 2, then dZm and p2 Zm are adjacent. Therefore
d = p2 . If β1 ≥ 2, then dZm and p1 Zm are adjacent. Thus β1 = 1. If α2 ≥ 2, then
dZm and p22 Zm are adjacent. So α2 = 1. Then m = pα1 1 p2 and n = p1 or n = p1 p2 . If
n = p1 , then by Corollary 3, Gn (Zm ) is a null graph, a contradiction. Therefore n = p1 p2 ,
m = pα1 1 p2 and α1 ≥ 2, in which case dZm is an isolated vertex of Gn (Zm ). Moreover,
A = {pr11 p2 Zm : 0 ≤ r1 ≤ α1 − 1} and V (Gn (Zm )) \ A = {pr11 Zm : 1 ≤ r1 ≤ α1 }.
Clearly, pr11 Zm and pr12 Zm are adjacent, where 1 ≤ r1 < r2 ≤ α1 . This implies that
Gp1 p2 (Zpα1 p2 ) = Kα1 ∪ Kα1 , where α1 ≥ 2. Next, suppose that s = 1. Since Gn (Zm ) is
1

not a null graph, by Corollary 3, we conclude that β1 ≥ 3. Therefore dZm is adjacent to
p1 Zm or p21 Zm . This completes the proof.



Lemma 2. Let Zn be a Zm -module. If Gn (Zm ) is not a null graph, then
|A| =

(

α1 ,
Qs

i=1 (αi

if n = p1 p2 , m = pα1 1 p2 and α1 ≥ 2;
− βi + 1) − 1, otherwise.

Proof. By Lemma 1, we know that if n = p1 p2 , m = pα1 1 p2 and α1 ≥ 2, then |A| = α1 .
Otherwise, from Lemma 1, we find that dZm is an isolated vertex of Gn (Zm ) if and only
5

if n divides d. So A = {dZm : n divides d, d divides m, d 6= m} = {pr11 · · · prss Zm : βi ≤
Q
ri ≤ αi } \ {0}. This implies that |A| = si=1 (αi − βi + 1) − 1 and the proof is complete.
Corollary 4. Let Zn be a Zm -module. Then Gn (Zm ) contains no isolated vertex if and
only if n = m 6= p1 , p21 , p1 p2 .
Proof. One side is obvious. For the other side assume that Gn (Zm ) contains no isolated
vertex. Hence n = m. By Corollary 3 and Lemma 2, it is clear that m 6= p1 , p21 , p1 p2 .



Theorem 2. Let Zn be a Zm -module. If Gn (Zm ) is not a null graph, then

α(Gn (Zm )) =

(

α1 + 1,
if n = p1 p2 , m = pα1 1 p2 and α1 ≥ 2;
Qs
′
i=1 (αi − βi + 1) − 1 + s , otherwise.

Proof. By Lemma 1, it is clear that if n = p1 p2 , m = pα1 1 p2 and α1 ≥ 2, then
α(Gn (Zm )) = α1 + 1. Otherwise, with no loss of generality we may assume that S ′ =
o
n
Q
β −1 Q
αi
αi
′ . Obviously, n ∤ pβj −1
{1, . . . , s′ }. Let B = A ∪ pj j
p
Z
:
1
≤
j
≤
s
m
j
i6=j pi ,
i6=j i
β −1 Q
αi
for every j, 1 ≤ j ≤ s′ . Hence by Lemma 1, pj j
i6=j pi Zm is not an isolated vertex,

for every j, 1 ≤ j ≤ s′ . Also, it is easy to see that B is an independent set and so
Q
α(Gn (Zm )) ≥ |A| + s′ = si=1 (αi − βi + 1) − 1 + s′ . Moreover, if C is an independent set

of Gn (Zm ) \ A and |C| ≥ s′ + 1, then by Pigeonhole Principle we conclude that there exist
Qs
Qs
ri′
ri
′
′
i=1 pi Zm ,
i=1 pi Zm ∈ C such that rj , rj < βj , for some j, 1 ≤ j ≤ s . This implies
′
Qs
Q
r
that i=1 pri i Zm and si=1 pi i Zm are adjacent, which is impossible. Therefore
α(Gn (Zm )) =

Qs

i=1 (αi

− βi + 1) − 1 + s′ .


We denote {i ∈ S : ri < βi } by Dd , where d = pr11 · · · prss is a divisor of m. Obviously,
Dd ⊆ S ′ .
Theorem 3. Let Zn be a Zm -module and d = pr11 · · · prss (6= 1, m) be a divisor of m. If n
divides d, then deg(dZm ) = 0 and otherwise
deg(dZm ) =

s
Y
Y
Y
(αi + 1) − 2 −
(αi + 1)
(αi − βi + 1).
i=1

i∈D
/ d

6

i∈Dd

Proof. If n|d, then dZm is an isolated vertex and so deg(dZm ) = 0. Assume that n
does not divide d. Then Dd is nonempty. Clearly, dZm and pt11 · · · ptss Zm are not adjacent
if and only if ti ≥ βi for each i ∈ Dd . Thus the number of vertices not adjacent to
Q
Q
dZm is i∈D
i∈Dd (αi − βi + 1) − 1 and hence the number of its neighbors is
/ d (αi + 1)
Q
Qs
Q

i∈Dd (αi − βi + 1).
i=1 (αi + 1) − 2 −
i∈D
/ d (αi + 1)
Suppose that Zn is a Zm -module and Gn (Zm ) is not a null graph. If
Q
Q
n = p1 · · · ps , then ∆(Gn (Zm )) = si=1 (αi + 1) − 2 − (α1 + 1) si=2 αi , where α1 ≥ · · · ≥ αs
Q
Q
and otherwise ∆(Gn (Zm )) = si=1 (αi + 1) − 2 − si=1 (αi − βi + 1).
Theorem 4.

Proof. First, suppose that n = p1 · · · ps . By Theorem 3, if d = pr11 · · · prss is a divisor of
Q
Q
Q
m and n does not divide d, then deg(dZm ) = si=1 (αi + 1) − 2 − i∈D
i∈Dd αi .
/ d (αi + 1)
Q
Q
If α1 ≥ · · · ≥ αs , then deg(dZm ) = ∆(Gn (Zm )) if and only if i∈D
i∈Dd αi =
/ d (αi + 1)
Qs
(α1 + 1) i=2 αi . Let {i ∈ S : αi = α1 } = {1, . . . , k} for some k, 1 ≤ k ≤ s. In
fact, {pri i Zm : 1 ≤ i ≤ k, 1 ≤ ri ≤ αi } is the set of all vertices with maximum degree. So
Q
Q
∆(Gn (Zm )) = si=1 (αi + 1) − 2 − (α1 + 1) si=2 αi .

Now, assume that there is an integer j such that βj 6= 1. We claim that there exist
Q
some vertices adjacent to all non-isolated vertices and so ∆(Gn (Zm )) = si=1 (αi + 1) − 2 −
Qs
i=1 (αi − βi + 1). If βj = 0, then pj Zm is adjacent to all non-isolated vertices. Otherwise,
β −1

βj ≥ 2. With no loss of generality suppose that S ′ = {1, . . . , s′ }. Let d = p1β1 −1 · · · ps′s′
Then dZm is adjacent to all non-isolated vertices. The claim is proved.

Theorem 5.

.



Let Zn be a Zm -module. Then Gn (Zm ) has a vertex which is adjacent to

all other vertices if and only if n = m and αj ≥ 2, for some j, 1 ≤ j ≤ s.
Proof. If Gn (Zm ) has a vertex which is adjacent to all other vertices, then Gn (Zm )
has not any isolated vertex. This implies that n = m. By contradiction suppose that
α1 = · · · = αs = 1. Let dZm be a vertex of Gn (Zm ) such that it is adjacent to all other
vertices. With no loss of generality, we may assume that d = p1 · · · pt , where 1 ≤ t < s.
Let d′ = pt+1 · · · ps . It is easy to see that dZm and d′ Zm are non-adjacent, a contradiction.
Therefore αj ≥ 2, for some j, 1 ≤ j ≤ s. Conversely, if n = m and αj ≥ 2, for some j,
1 ≤ j ≤ s, then by Corollary 4, Gn (Zm ) has no isolated vertex. Also, in view of the proof
of Theorem 4, we find that Gn (Zm ) has a vertex which is adjacent to all other vertices.
The following corollary is a generalization of [9, Theorem 2.9].
7

Corollary 5. Let Zn be a Zm -module. Then Gn (Zm ) is a complete graph if and only if
n = m = pα1 1 and α1 ≥ 2.
Proof. Suppose that Gn (Zm ) is a complete graph. By Theorem 5, we find that n = m
Qs−1 αi
pi Zm are two
and αj ≥ 2, for some j, 1 ≤ j ≤ s. If s ≥ 2, then pαs s Zm and i=1

non-adjacent vertices which is a contradiction. Therefore n = m = pα1 1 and α1 ≥ 2. The

other side is obvious.



Theorem 6. Let Zn be a Zm -module. If Gn (Zm ) is not a null graph, then
γ(Gn (Zm )) =

(

|A| + 1, if n 6= p1 · · · ps or n = p1 p2 , m = pα1 1 p2 and α1 ≥ 2;
|A| + 2, otherwise.

Proof. Suppose that n 6= p1 · · · ps . In view of the proof of Theorem 4, Gn (Zm ) has a
vertex which is adjacent to every non-isolated vertices. This implies that γ(Gn (Zm )) =
|A| + 1. Next, assume that n = p1 · · · ps . If s = 1, then Gn (Zm ) is a null graph. Now,
assume that s ≥ 2. If n = p1 p2 , m = pα1 1 p2 and α1 ≥ 2, then by Lemma 1, γ(Gn (Zm )) =
|A| + 1. Otherwise, let B = {p1 Zm , p2 · · · ps Zm }. If dZm is a non-isolated vertex, then n
does not divide d. If p1 ∤ d, then dZm is adjacent to p2 · · · ps Zm . Otherwise, pj ∤ d, for some
j, 2 ≤ j ≤ s. Therefore pj ∤ [d, p1 ]. This yields that dZm is adjacent to p1 Zm . Therefore B
is a dominating set for Gn (Zm ) \ A. Now, we claim that Gn (Zm ) has not a vertex which is
adjacent to every non-isolated vertices. By contradiction, suppose that dZm is adjacent to
every non-isolated vertices. Since n ∤ d, we may assume that d = p1 · · · pt , where 1 ≤ t < s.
Let d′ = pt+1 · · · ps . Clearly, dZm and d′ Zm are non-adjacent. Since n ∤ d, by Theorem 1,
d′ Zm is not an isolated vertex, a contradiction. Thus γ(Gn (Zm )) = |A| + 2.

3



Chromatic Index of Gn (Zm)

In this section, we study the chromatic index of Gn (Zm ). First, we need the following
theorems:
Theorem A. [8, Theorem 17.4] (Vizing’s Theorem) If G is a simple graph, then either
χ′ (G) = ∆(G) or χ′ (G) = ∆(G) + 1.
Theorem B. [7, Corollary 5.4] Let G be a simple graph. Suppose that for every vertex
8

u of maximum degree, there exists an edge u — v such that ∆(G) − deg(v) + 2 is more
than the number of vertices with maximum degree in G. Then χ′ (G) = ∆(G).
Theorem C. [11, Theorem D] If G has order 2k and maximum degree 2k − 1, then
χ′ (G) = ∆(G). If G has order 2k + 1 and maximum degree 2k, then χ′ (G) = ∆(G) + 1 if
and only if the size of G is at least 2k2 + 1.
Theorem 7. Suppose that Zn is a Zm -module and Gn (Zm ) is not a null graph. If n = pβ1 1 ,
Q
then χ′ (Gn (Zm )) = ∆(Gn (Zm )) if and only if β1 si=2 (αi + 1) is an odd integer.
Proof. Clearly, the set of all non-isolated vertices of Gn (Zm ) is equal to {dZm : d =
pr11 · · · prss , d 6= 1, 0 ≤ r1 ≤ β1 − 1 and 0 ≤ ri ≤ αi for i = 2, . . . , s}. So Gn (Zm ) \ A is a
Q
complete graph of order β1 si=2 (αi + 1) − 1. The result, now, follows from [4, Theorem
5.11].

Theorem 8.



Suppose that Zn is a Zm -module and Gn (Zm ) is not a null graph. If

n = p1 p2 and m = pα1 1 pα2 2 , then χ′ (Gn (Zm )) = ∆(Gn (Zm )) if and only if max{α1 , α2 } is
an even integer.
Proof. If α1 = α2 = 1, then Gn (Zm ) is a null graph. If α1 = 1 and α2 ≥ 2, then
r
Gn (Zm ) ∼
= Kα2 ∪ Kα2 . If α2 , α2 ≥ 2, then assume that Bi = {pi i Zm : 1 ≤ ri ≤ αi },
for i = 1, 2. Clearly, B1 ∪ B2 is the set of all non-isolated vertices of Gn (Zm ), every
Bi forms a complete graph and Gn (Zm ) \ A is the disjoint union of them. Therefore
Gn (Zm ) \ A ∼

= Kα1 ∪ Kα2 . Now, [4, Theorem 5.11] completes the proof.
Theorem 9.

Let Zn be a Zm -module. If n = p1 · · · ps and s ≥ 3, then χ′ (Gn (Zm )) =

∆(Gn (Zm )).
Proof. With no loss of generality assume that α1 ≥ · · · ≥ αs . Let {i ∈ S : αi = α1 } =
{1, . . . , k} for some k, 1 ≤ k ≤ s. By Theorem 4, we know that {pri i Zm : 1 ≤ i ≤ k, 1 ≤
ri ≤ αi } is the set of all vertices with maximum degree. Hence Gn (Zm ) has kα1 vertices
Q
with maximum degree. On the other hand, we know that ∆(Gn (Zm )) = si=1 (αi + 1) −
Q
Q
Qs−1
2 − (α1 + 1) si=2 αi and deg(p1 · · · ps−1 Zm ) = si=1 (αi + 1) − 2 − αs i=1
(αi + 1). It
is easy to check that if s ≥ 4, then ∆(Gn (Zm )) − deg(p1 · · · ps−1 Zm ) + 2 is more than

α1 + · · · + αs and so ∆(Gn (Zm )) − deg(p1 · · · ps−1 Zm ) + 2 is more than the number of
9

vertices with maximum degree. Note that deg(prss Zm ) = ∆(Gn (Zm )) (1 ≤ rs ≤ αs ) if and
only if α1 = · · · = αs . Also, if s ≥ 4, then ∆(Gn (Zm )) − deg(p2 · · · ps Zm ) + 2 is more than
sα1 . Therefore by Theorem B, we find that χ′ (Gn (Zm )) = ∆(Gn (Zm )). Now, consider
s = 3. If α3 ≥ 2, then it is easy to see that ∆(Gn (Zm )) − deg(p1 · · · ps−1 Zm ) + 2 is more
than α1 + α2 + α3 and the proof is complete. Therefore assume that α3 = 1. There are
two following cases:
Case 1. α2 = 1. If α1 = 1, then n = m and so Gn (Zm ) = G(Zm ). One can easily
check that χ′ (G(Zp1 p2 p3 )) = ∆(G(Zp1 p2 p3 )) = 4 (see [9, Fig. 3]). If α1 ≥ 2, then Gn (Zm )
has α1 vertices with maximum degree. Also, ∆(Gn (Zm )) − deg(p1 p3 Zm ) + 2 is more than
α1 and the result, follows from Theorem B.
Case 2. α2 ≥ 2. In this case, it is easy to see that ∆(Gn (Zm )) − deg(p2 p3 Zm ) + 2 is
more than α1 + α2 . Also, ∆(Gn (Zm )) − deg(p1 p3 Zm ) + 2 is more than α1 + α2 and the
result, follows from Theorem B.
Theorem 10.



Let Zn be a Zm -module. If n 6= p1 · · · ps and s ≥ 2, then χ′ (Gn (Zm )) =

∆(Gn (Zm )).
Q
Q
Proof. By Theorem 4, we know that Gn (Zm ) has si=1 (αi + 1) − 1 − si=1 (αi − βi + 1)
Q
Q
non-isolated vertices and ∆(Gn (Zm )) = si=1 (αi +1)−2− si=1 (αi −βi +1). Hence by TheQ
Q
orem C, we find that χ′ (Gn (Zm )) = ∆(Gn (Zm )), where si=1 (αi +1)−1− si=1 (αi −βi +1)
Q
Q
is even. Next, assume that si=1 (αi + 1) − 1 − si=1 (αi − βi + 1) is odd. Since the size

of a complete graph of order 2k + 1 is 2k2 + k, if we prove that Gn (Zm ), in this case,

Qs
Qs
losses at least k =
i=1 (αi + 1) − 2 −
i=1 (αi − βi + 1) /2 edges, then by Theorem
Q
C, χ′ (Gn (Zm )) = ∆(Gn (Zm )). Let d = si=1 pri i be a divisor of m such that n ∤ d and
Q
Q′
{i ∈ S ′ : ri ≥ βi } =
6 ∅. Let {i ∈ S ′ : ri ≥ βi } = {1, . . . , t}. Set d = si=t+1 pβi i si=s′ +1 pri i .
It is easy to check that dZm and dZm are not adjacent. So we conclude that Gn (Zm )

Qs
Qs
Qs ′
Qs
losses at least
(α
+
1)
−
(α
−
β
+
1)
−
β
(α
+
1)
/2 edges. We
′
i
i
i
i
i
i=1
i=1
i=1
i=s +1
continue the proof in the following two cases:

Case 1. βi ≥ 2, for some i, 1 ≤ i ≤ s′ . With no loss of generality we may aso
n Q′
sume that βs′ ≥ 2. Suppose that B = pr11 si=2 pβi i Zm : 0 ≤ r1 ≤ β1 − 1 and C =
o
n
Q
pβ1 1 si=2 pri i Zm : 0 ≤ ri ≤ βi − 1, for 2 ≤ i ≤ s′ and otherwise 0 ≤ ri ≤ αi . Clearly, every element of B is not adjacent to every element of C. This implies that Gn (Zm ) losses at
Q
Q′
Q′
least si=1 βi si=s′ +1 (αi + 1) − ( si=2 βi + β1 − 1) new edges. Therefore Gn (Zm ) losses at
Q
Q′
Q
Q
Q′
least l = ( si=1 (αi + 1)− si=1 (αi − βi + 1)+ si=1 βi si=s′ +1 (αi + 1))/2− ( si=2 βi + β1 − 1)

edges. It suffices we prove that k ≤ l. One can easily see that k ≤ l if and only if
Q
Q
Q′
2(β1 − 2) ≤ (β1 si=s′ +1 (αi + 1)− 2) si=2 βi . Since βs′ ≥ 2, so 2(β1 − 2) ≤ (β1 si=s′ +1 (αi +
10

1) − 2)

Q s′

i=2 βi

and hence k ≤ l.

Case 2. β1 = · · · = βs′ = 1. Clearly,

Qs ′

i=2 pi Zm

and p1

Qs

ri
i=s′ +1 pi Zm

are non-

adjacent, where 0 ≤ ri ≤ αi , for i = s′ + 1, . . . , s . This implies that Gn (Zm ) losses at
Q
Q
least si=s′ +1 (αi + 1) − 1 new edges. Therefore Gn (Zm ) losses at least l = ( si=1 (αi + 1) −
Qs
Qs
i=1 (αi − βi + 1) +
i=s′ +1 (αi + 1))/2 − 1 edges. In this case, k ≤ l is obvious and the

proof is complete.



From the above theorems, we can deduce the next result.
Corollary 6. Let Zn be a Zm -module. If Gn (Zm ) is not a null graph, then χ′ (Gn (Zm )) =
∆(Gn (Zm )), unless the following cases:
(i) n = pβ1 1 and β1

Qs

i=2 (αi

+ 1) is even.

(ii) n = p1 p2 , m = pα1 1 pα2 2 and max{α1 , α2 } is odd.

4

Eulerian Tour in Gn (Zm)

An Eulerian tour in a graph is a closed trail including all the edges of the graph. A graph
is Eulerian if it has an Eulerian tour. By [8, Theorem 4.1], a simple connected graph is
Eulerian if and only if it has no vertices of odd degree. In this section, we determine all
integer numbers n and m for which Gn (Zm ) \ A is an Eulerian graph. We start with the
following theorem.
Theorem 11. Let Zn be a Zm -module. If Gn (Zm ) is not a null graph, then diam(Gn (Zm )\
A) ≤ 4, except for the case n = p1 p2 , m = pα1 1 p2α2 and α1 , α2 ≥ 2, in which case
Gn (Zm ) \ A ∼
= Kα1 ∪ Kα2 .
Proof. Assume that Gn (Zm ) is not a null graph. In view of the proof of Theorem 6, we
conclude that if n 6= p1 · · · ps , then Gn (Zm ) \ A is connected and diam(Gn (Zm ) \ A) ≤ 2.
Now, suppose that n = p1 · · · ps . Since Gn (Zm ) is not a null graph, so s 6= 1. First assume
that s ≥ 3. By the proof of Theorem 6, we know that {p1 Zm , p2 · · · ps Zm } is a dominating
set for Gn (Zm ) \ A. Since s ≥ 3, p2 Zm is adjacent to both p1 Zm and p2 · · · ps Zm . This
implies that Gn (Zm ) \ A is connected and diam(Gn (Zm ) \ A) ≤ 4. Next, assume that
s = 2. By Lemma 1, if n = p1 p2 , m = pα1 1 p2 and α1 ≥ 2, then diam(Gn (Zm ) \ A) = 1.
Now, consider n = p1 p2 , m = pα1 1 pα2 2 and α1 , α2 ≥ 2. As we saw in the proof of Theorem
8, Gn (Zm ) \ A ∼

= Kα1 ∪ Kα2 and the proof is complete.
11

Now, we are in a position to generalize Theorem 5.1 of [9].
Theorem 12.

Suppose that Zn is a Zm -module and Gn (Zm ) is not a null graph. Then

Gn (Zm ) \ A is an Eulerian graph if and only if one of the following holds:
(i) αi and βi are even integers for each i, 1 ≤ i ≤ s.
(ii) αi is an odd integer and βi is an even integer for some i, 1 ≤ i ≤ s.
(iii) n = p1 · · · ps and m = pα1 1 · · · pαs s , where αi ’ are odd integers and s ≥ 3.
(iv) n = p1 p2 and m = pα1 1 p2 , where α1 > 1 is an odd integer.
Proof. By Theorem 3, Gn (Zm ) \ A is an Eulerian graph if and only if for each nonQ
Q
Q
isolated vertex dZm of Gn (Zm ) both si=1 (αi + 1) and i∈D
i∈Dd (αi − βi + 1)
/ d (αi + 1)

are even or odd integers. So the “if” part of theorem is obvious. For the converse,
Q
suppose that Gn (Zm ) \ A is an Eulerian graph. First assume that both si=1 (αi + 1)
Q
Q
and i∈D
i∈Dd (αi − βi + 1) are odd integers for a vertex dZm of Gn (Zm ) \ A.
/ d (αi + 1)

Thus all αi ’ are even integers. If βi is an odd integer for some i, 1 ≤ i ≤ s, then there

exists a vertex d′ Zm such that Dd′ = {i}. (Note that Gn (Zm ) is not a null graph.) So
Q
Q
′
i∈D
/ ′ (αi + 1)
i∈D ′ (αi − βi + 1) is an even integer which implies that deg(d Zm ) is an
d

d

odd integer, a contradiction. Therefore βi is an even integer for each i, 1 ≤ i ≤ s. Next,
Q
Q
Q
assume that both si=1 (αi + 1) and i∈D
i∈Dd (αi − βi + 1) are odd integers for a
/ d (αi + 1)

vertex dZm of Gn (Zm ) \ A. Hence αi is an odd integer for some i, 1 ≤ i ≤ s. With no loss

of generality suppose that {i ∈ S : αi is an odd integer} = {1, . . . , t}, where 1 ≤ t ≤ s.
Suppose that β1 , . . . , βt are odd integers. If n = p1 · · · ps and m = pα1 1 · · · pαs s , where αi ’ are
odd integers, then we are done. (Note that Gn (Zm ) \ A is a connected graph.) Otherwise
Q
Q
there exists a vertex d′ Zm such that Dd′ = {1, . . . , t}. So i∈D
/ d′ (αi +1)
i∈Dd′ (αi −βi +1)
is an odd integer which implies that deg(d′ Zm ) is an odd integer, a contradiction. Thus

βi is an even integer for some i, 1 ≤ i ≤ t. The proof is complete.



References
[1] S. Akbari, S. Khojasteh, Commutative rings whose cozero-divisor graphs are unicyclic or of bounded degree, Comm. Algebra, 42 (2014), 1594–1605.
[2] S. Akbari, S. Khojasteh, A. Yousefzadehfard, The proof of a conjecture in Jacobson
graph of a commutative ring, J. Algebra Appl., Vol. 14, No. 10 (2015) 1550107.
12

[3] S. Akbari, H.A. Tavallaee, S. Khalashi Ghezelahmad, Intersection graph of submodules of a module, J. Algebra Appl. 11 (2012), Article No. 1250019.
[4] I. Anderson, A First Course in Discrete Mathematics, Springer-Verlag, 2001.
[5] D.F. Anderson, P.S. Livingston, The zero-divisor graph of a commutative ring, J.
Algebra, 217 (1999), 434–447.
[6] S.E. Atani, A. Yousefian Darani, E.R. Puczylowski, On the diameter and girth
of ideal-based zero-divisor graphs, Publicationes Mathematicae Debrecen, 78:3-4
(2011) 607–612.
[7] L.W. Beineke, B.J. Wilson, Selected Topics in Graph Theory, Academic Press Inc.,
London, 1978.
[8] J.A. Bondy, U.S.R. Murty, Graph Theory, Graduate Texts in Mathematics, 244
Springer, New York, 2008.
[9] I. Chakrabarty, S. Ghosh, T.K. Mukherjee, M.K. Sen, Intersection graphs of ideals
of rings, Discrete Mathematics, 309 (2009), 5381–5392
[10] B. Csákány and G. Pollák, The graph of subgroups of a finite group (Russian),
Czech. Math. J. 19 (1969), 241–247.
[11] M.J. Plantholt, The chromatic index of graphs with large maximum degree, Discrete
Math. 47 (1981), 91–96.

13

