arXiv:1401.6619v1 [math.AC] 26 Jan 2014

ON CYCLES IN INTERSECTION GRAPHS OF RINGS
A. AZIMI, A. ERFANIAN, M. FARROKHI D. G., AND N. HOSEINI
Abstract. Let R be a commutative ring with non-zero identity. We describe
all C3 - and C4 -free intersection graph of non-trivial ideals of R as well as Cn free intersection graph when R is a reduced ring. Also, we shall describe all
complete, regular and n-claw-free intersection graphs. Finally, we shall prove
that almost all Artin rings R have Hamiltonian intersection graphs. We show
that such graphs are indeed pancyclic.

1. Introduction
If S = {S1 , . . . , Sn } is a family of sets, then the intersection graph of S, is the
graph having S as its vertex set with Si adjacent to Sj if i 6= j and Si ∩ Sj 6= ∅.
A well-know theorem due to Marczewski [8] states that all graphs are intersection
graph.
An interesting case of intersection graphs is when the members of S have an algebraic structure. Bosak [1] was the first who studied graphs arising from semigroups.
Csákéany and Pollák [3] defined and studied the intersection graphs of nontrivial
proper subgroups of groups. Zelinka [10] continued the work of Csákéany and
Pollák on intersection graphs of subgroups of finite abelian groups, and later Shen
[9] studies such graphs and classifies all finite groups whose intersection graphs of
nontrivial subgroups are disconnected. Herzog, Longobardi and Maj [4] study the
intersection graphs of maximal subgroups of finite groups and among other results
classify all finite groups with disconnected graph. The same as for groups, the intersection graphs of ideals of rings and subspaces of vector spaces have been discussed
in [2, 5, 6].
Let R be a commutative ring with a non-zero identity. The intersection graph
of R, denoted by Γ(R), is a graph whose vertices are the nontrivial ideals of R and
two distinct vertices are joined by an edge if the corresponding ideals of R have a
non-zero intersection.
In this paper, we study the cycle structure of intersection graphs. First we
classify all Artin rings with a regular (hence complete) intersection graph. Next we
shall investigate all rings R whose intersection graphs Γ(R) do not have an induced
cycle of length 3 or 4. Also, we show that if R is a reduce ring, then Γ(R) is Cn -free
(n ≥ 5) if and only if R has no ideal which is the direct sum of n non-zero ideals.
The same result is also established for n-claws instead of n-cycles. In the last
section, we shall prove that except few cases all other Artin rings have Hamiltonian
intersection graphs. Using simple modifications of the given Hamiltonian cycle, we
show that Γ(R) is pancyclic whenever it is Hamiltonian. Recall that an n-claw (a
2000 Mathematics Subject Classification. Primary 05C25, 05C45; Secondary 16P20.
Key words and phrases. Intersection graph, cycle, claw, Hamiltonian, pancyclic.
1

2

A. AZIMI, A. ERFANIAN, M. FARROKHI D. G., AND N. HOSEINI

claw) is the star graph K1,n (K1,3 ). Also a graph is called pancyclic if it contains
cycles of possible arbitrary sizes ≥ 3.
The following theorem will be used without further reference.
Theorem ([7, Theorem VI.2]). Let R be an Artin commutative ring with a non-zero
identity. Then
R = R1 ⊕ · · · ⊕ Rn ,
where R1 , . . . , Rn are local rings.
If R is a ring, then the ideals a1 , . . . , an are called independent if
ai ∩ (a1 + · · · + ai−1 + ai+1 + · · · + an ) = 0
for i = 1, . . . , n. In other words, (a1 , . . . , an ) = a1 ⊕ · · · ⊕ an is the direct sum of
a1 , . . . , an . All rings in this paper are commutative rings with a non-zero identity.
2. Cn -free intersection graphs
As a most simple property we may investigate on intersection graph Γ(R) of
ideals of a ring, is whether Γ(R) is a complete graph. We show that the class of
Artin rings with a complete intersection graph coincides with the class of Artin
rings with a regular intersection graph and then characterize all such rings.
Theorem 2.1. Let R be an Artin ring, which is not a direct sum of two fields. If
Γ(R) is regular, then it is complete.
Proof. First we show that R has no direct factor, which is a field. If R = S ⊕ F ,
where F is a field and S is not a field, then NΓ(R) (F ) = {a ⊕ F : 0 6= a ⊳ S} and
NΓ(R) (S) = {a, a ⊕ F : 0 6= a ⊳ S}. Hence, degΓ(R) S > degΓ(R) F , which is a
contradiction. Therefore, each maximal ideal of R is adjacent to all other vertices
of Γ(R), from which it follows that Γ(R) is a complete graph.

Theorem 2.2. If R is an Artin ring, then the graph Γ(R) is complete if and only
if there exists a sequence of rings R1 , . . . , Rn , in which R = R1 , (Ri , Ri+1 ) is a
local ring for all i = 1, . . . , n − 1 and Rn is a field.
Proof. If R is not a local ring, then R = S ⊕ T for some non-zero rings S and
T . But then S ∩ T = 0, which is a contradiction. Thus R = (R, m) is a local
ring. Continuing this way for m instead of R the result follows. The converse is
obvious.

In the following two theorems, we shall consider conditions under which the
intersection graph of a ring is a star graph, which also results in a characterization
of rings with a bipartite intersection graph.
Theorem 2.3. Let R be a ring, which is neither a direct sum of two fields nor a
direct sum of a field with a local ring (S, m) such that m is a field. If Γ(R) has a
pendant, then Γ(R) is a star graph.
Proof. Let a ∈ V (Γ(R)) be a pendant. If a is a maximal ideal, then it is easy to see
that R = (R, a) is a local ring and a = (x) is a principal ideal. Let b be the ideal
of R adjacent to a. Then b = (x2 ) and (x3 ) = 0, hence Γ(R) is an edge.
If a is not a maximal ideal, then there exists a unique maximal ideal m of R
containing a. Clearly, a = (x) is principal and (x2 ) = 0. If R is not a local ring,
then there exists a maximal ideal n such that a ∩ n = 0. Thus R = a ⊕ n and

INTERSECTION GRAPH

3

a is a field. Then m = a + b for some ideal b of n. But then (n, b) is a local
ring such that b is a field, which is a contradiction. Therefore (R, m) is a local
ring. Clearly, m = (x, y) for some y ∈ R. If m is principal, then we may assume
that m = (y). Thus (y 2 ) = (x) and (y 3 ) = 0, which implies that Γ(R) is an
edge. If m is not principal, then (x) ∩ (y) = 0 and consequently xy = 0. Since
(x) ⊆ (x) + (y 2 ) ⊆ (x) + (y) = m, it follows that (y 2 ) = 0. Hence m2 = 0 so that
m is a vector space over the field F = R/m, where the multiplication is defined
by (r + m) · m = rm for all r ∈ R and m ∈ m. Clearly, there is a one to one
correspondence between ideals of R contained in m and subspaces of (m, F ). Hence
dimF m = 2 so that Γ(R) is a star graph.

Theorem 2.4. If Γ(R) is triangle-free, then Γ(R) is star or two isolated vertices.
Proof. If R is not a local ring, then there exist two distinct maximal ideals m1
and m2 in R. Since Γ(R) is triangle-free, we should have m1 ∩ m2 = 0. Hence
R = m1 ⊕ m2 . Let F1 = R/m1 and F2 = R/m2 . Then R ∼
= F1 ⊕ F2 and Γ(R) is the
union of two isolated vertices.
Now, suppose that (R, m) is a local ring. We have two cases for m.
Case 1: m is not a principal ideal. First we show that m2 = 0. If x ∈ m and
y ∈ m \ xR, then xR ∩ yR = 0. Thus xy = 0 so that (m \ xR)x = 0. On the
other hand, if r ∈ R, then xr = y + (xr − y) so that xrx = 0. Thus xRx = 0 and
consequently mx = 0. Hence m2 = 0.
Let F = R/m. The same as in the proof of Theorem 2.3, (m, F ) is a vector
space. If dimF m ≥ 3 and {x, y, z} is an independent set in (m, F ), then the set
of ideals {(x), (x, y), (x, y, z)} induces a triangle in Γ(R), which is a contradiction.
Thus dimF m ≤ 2.
If dimF m = 2, then every two distinct non-trivial ideals of R different from m
are disjoint. Thus Γ(R) is a star graph with m at the center. If dimF m = 1, then
Γ(R) is a single vertex and we are done.
Case 2: m = xR is a principal ideal. Let a be a non-zero ideal of R. Then
a ⊆ m. If y ∈ a, then y = rx for some r ∈ R. If r is a unit, then x = yr−1 ∈ a
and hence a = m. If a 6= m, then r is not unit and so r = sx, for some s ∈ R.
Thus y = sx2 and subsequently a ⊆ m2 ⊆ m. Since Γ(R) is triangle free, it follows
that a = m2 . Therefore Γ(R) is either a single vertex when m = m2 or it is an edge
when m 6= m2 .

The following corollary is a direct consequence of the preceding two theorems.
Corollary 2.5. Let R be a ring, which is neither a direct sum of two fields nor
a direct sum of a field with a local ring (S, m) such that m is a field. Then the
following conditions are equivalent:
(1) Γ(R) is triangle-free,
(2) Γ(R) has a pendant,
(3) Γ(R) is bipartite.
(4) Γ(R) is star.
In what follows, we shall concentrate on cycle structure of intersection graphs
and give a characterization of almost all intersection graphs under investigation
that do not have an induced cycle of length greater than 3.
Theorem 2.6. The graph Γ(R) is C4 -free if and only if R has no set of four
non-zero independent ideals.

4

A. AZIMI, A. ERFANIAN, M. FARROKHI D. G., AND N. HOSEINI

Proof. First suppose that R has an ideal which is a direct sum of four non-zero
ideals, namely a1 , a2 , a3 and a4 . Then a1 ⊕ a2 , a2 ⊕ a3 , a3 ⊕ a4 , a4 ⊕ a1 induces a
cycle of length 4 in Γ(R).
Conversely, suppose that R has an induced 4-cycle with vertices a1 , a2 , a3 and
a4 . Then a1 ∩ a3 = a2 ∩ a4 = 0. Since a2 ∩ a3 + a3 ∩ a4 ⊆ a3 , we have
(a1 ∩ a2 ) ∩ (a2 ∩ a3 + a3 ∩ a4 + a4 ∩ a1 ) ⊆ (a1 ∩ a2 ) ∩ (a3 + (a4 ∩ a1 ))
= (a1 ∩ a2 ) ∩ (a3 ⊕ a4 ∩ a1 ).
If a + b ∈ (a1 ∩ a2 ) ∩ (a3 ⊕ a4 ∩ a1 ), where a ∈ a3 and b ∈ a4 ∩ a1 , then a ∈ a1 , which
implies that a = 0. Then b ∈ a2 and similarly b = 0. Hence
(a1 ∩ a2 ) ∩ (a2 ∩ a3 + a3 ∩ a4 + a4 ∩ a1 ) = 0.
Similar arguments show that (a1 ∩ a2 ), (a2 ∩ a3 ), (a3 ∩ a4 ) and (a4 ∩ a1 ) are non-zero
independent ideals and the proof is complete.

Recall that a ring is reduced if it has no non-zero nilpotent element.
Theorem 2.7. Let R be a reduced ring. Then Γ(R) is Cn -free (n ≥ 5) if and only
if R has no set of n independent of ideals.
Proof. First suppose Γ(R) is Cn -free. If R has n non-zero independent ideals
a1 , . . . an , then a1 ⊕ a2 , a2 ⊕ a3 , . . . , an ⊕ a1 induces a cycle of length n in Γ(R),
which is a contradiction.
Now, suppose that R has no set of n non-zero independent ideals and the ideals
a1 , . . . , an induce a cycle of length n. Let bn = an ∩ a1 and bi = ai ∩ ai+1 for
all i = 1, . . . , n − 1. Then for all distinct 1 ≤ i, j ≤ n, we have bi bj = 0. Let
b∗i = b1 + · · · + bi−1 + bi+1 + · · · + bn . Then bi b∗i = 0. Thus (bi ∩ b∗i )2 ⊆ bi b∗i = 0,
for all i = 1, . . . , n. Since R is reduced, it follows that bi ∩ b∗i = 0, from which it
follows that {b1 , . . . , bn } is a set of non-zero independent ideals of R, which is a
contradiction.

In the sequel, we give another approaches to induced cycles in intersection graphs.
The following lemma is straightforward.
Lemma 2.8. Suppose a1 , . . . , an induce a cycle of length n in Γ(R). Then there
exist t independent ideals ai1 , . . . , ait such that 2 ≤ t ≤ ⌊ n2 ⌋ and ai1 ⊕ · · · ⊕ ait is
adjacent to ai for all i = 1, . . . , n.
Theorem 2.9. Suppose a1 , . . . , an induce a cycle of length n in Γ(R) and the
number t introduced in the previous lemma takes it maximum value ⌊ n2 ⌋. Then R
has a set of n non-zero independent ideals if n is even and it has a set of n − 1
non-zero independent ideals if n is odd.
Proof. Without loss of generality we may assume that a1 , a3 , . . . , a2⌊ n2 ⌋−1 are independent. A simple verification shows that
{a1 ∩ a2 , a2 ∩ a3 , . . . , an−1 ∩ an , an ∩ a1 }
when n is even,
{a1 ∩ a2 , a2 ∩ a3 , . . . , a2⌊ n2 ⌋−1 ∩ an−1 , an ∩ a1 }
when n is odd are sets of non-zero independent ideas of R, as required.



INTERSECTION GRAPH

5

Theorem 2.10. Suppose a1 , . . . , an (n ≥ 3) are independent ideals of R. Let
bi = ai1 ⊕ · · · ⊕ aini , for i = 1, . . . , n. Then b1 , . . . , bn induce a cycle of length n if
and only if there exist a permutation π ∈ Sn such that bi = aπ(i) ⊕ aπ(i+1) .
Proof. If n = 3 then the result is obvious. If there exist π ∈ Sn such that bi =
aπ(i) ⊕ aπ(i+1) , for all i = 1, . . . , n, then there is nothing to prove. Hence we may
assume that b1 , . . . , bn are vertices of an induced cycle with length n ≥ 4. Then
ni ≥ 2, for all i = 1, . . . , n, otherwise bj = aj1 for some j. But then aj1 is adjacent
to bj−1 and P
bj+1 , which implies that bj−1 and bj+1 are adjacent, a contradiction.
n
ai is at most
Hence 2n ≤ i=1 ni . On the other hand, the
Pnumber of bj containingP
two for all i = 1, . . . , n, which implies that ni=1 ni ≤ 2n. Therefore ni=1 ni = 2n
and hence ni = 2, for all i = 1, . . . , n. Now the result is straightforward.

Utilizing the same method used before, we may prove the following result for
n-claws instead of n-cycles.
Theorem 2.11. Let R be a reduced ring. Then the ideals a1 , . . . , an of R are
independent and a1 ⊕ · · · ⊕ an is a proper ideal of R if and only if there exist an
induced n-claw in Γ(R).
Proof. If a1 , . . . , an are independent ideals of R such that a1 ⊕ · · · ⊕ an is a proper
ideal of R, then clearly {a1 , . . . , an , a1 ⊕ · · · ⊕ an } induces an n-claw in Γ(R).
Now, suppose that the ideals a1 , . . . , an and a are pendants and the center of an
induced n-claw, respectively. Let
a∗i = a1 + · · · + ai−1 + ai+1 + · · · + an ,
for all i = 1, . . . , n. Then
(ai ∩ a∗i )2 ⊆ ai a∗i =

X
j6=i

ai aj ⊆

X

ai ∩ aj = 0,

j6=i

for all i = 1, . . . , n, which implies that a1 , . . . , an are independent. If R 6= a1 ⊕ · · · ⊕
an , then we are done. Now, suppose that R = a1 ⊕ · · · ⊕ an . If ai is not a field for
some 1 ≤ i ≤ n, then by replacing ai by one of its non-zero proper ideals, we may
assume that R 6= a1 ⊕ · · · ⊕ an , as required. Otherwise a1 , . . . , an are all fields. But
then ai ⊆ a, for all i = 1, . . . , n, which implies that a = R, a contradiction.

3. Hamilton cycles
The aim of this section is to show that except few cases all intersection graphs
are Hamiltonian. Indeed, we shall prove the stronger result that such graphs are
pancyclic.
A simple verification shows that if R = S ⊕ F , where F is a field and Γ(S)
has a Hamiltonian path, then Γ(R) has a Hamiltonian cycle. This fact enables us
to prove the following result. In what follows, the set of all ideals of a ring R is
denoted by I(R).
Theorem 3.1. Let R be an Artin ring. Then Γ(R) is Hamiltonian if and only if
R is not isomorphic to the following rings:
(1) F or E ⊕ F ,
(2) S or E ⊕ S such that (S, F ) is a local ring,
(3) S such that (S, T ) is a local ring and (T, F ) is a local ring,
where E and F are fields.

6

A. AZIMI, A. ERFANIAN, M. FARROKHI D. G., AND N. HOSEINI

Proof. If R is isomorphic to one of the rings in parts (1), (2) or (3), then clearly
Γ(R) is not Hamiltonian. Now, suppose that R is a ring such that Γ(R) is not
Hamiltonian. We proceed in some steps:
Case 1: R = R1 ⊕ R2 such that |I(R1 )|, |I(R2 )| ≥ 4. Let
I(R1 ) = {0 = a0 , a1 , . . . , am = R1 }
and
I(R2 ) = {0 = b0 , b1 , . . . , bn = R2 }.
Clearly an arbitrary ideal of R can be expressed as ai ⊕ bj for some 1 ≤ i ≤ m and
1 ≤ j ≤ n. Consider an (m × n)-grid and put ai ⊕ bj on the (i, j)-th coordinate.
By Figures 1, 2 and 3, the subgraph induced by ideals ai ⊕ bj in which ai , bj 6= 0
is Hamiltonian with a Hamiltonian cycle in which there exists at least one edge on
every row as well as one edge on every column. If {ai ⊕ bj , ai+1 ⊕ bj } is an edge such
that i, j > 0, then by removing this edge and adding two edges {ai ⊕ bj , bj } and
{bj , ai+1 ⊕ bj } we reach to a new cycle including the vertex bj . Similarly, we may
enlarge the resulting cycle in which the new cyclic contains an arbitrary ai 6= 0.
Continuing this way, we reach to a Hamiltonian cycle for Γ(R), a contradiction.
Case 2: R = R1 ⊕ R2 such that I(R1 ) ≥ 3 and |I(R2 )| = 3. The same as in case
1, we may present ideals of R on the grids as it is shown in Figures 4 and 5, which
gives rise to a Hamiltonian cycle for Γ(R). Hence Γ(R) is Hamiltonian, which is a
contradiction.
Case 3: R = S ⊕ F , where F is a field. If S = S1 ⊕ S2 , where either S1 or S2 ,
say S1 is not a field, then R = S1 ⊕ (S2 ⊕ F ) and by case 1, Γ(R) is Hamiltonian.
Now, suppose that S1 and S2 are both fields. Then
S1 ∼ S1 ⊕ S2 ∼ S2 ∼ S2 ⊕ F ∼ F ∼ S1 ⊕ F ∼ S1
is a Hamiltonian cycle for Γ(R). Hence Γ(R) is Hamiltonian, a contradiction.
Case 4: If R is a field or it is a direct sum of two fields, then we are done. If
not, by cases 1, 2 and 3, there exists a sequence {(Si , Ri )}ni=1 of local rings and a
sequence {Fi }ni=1 of fields such that R = R0 = S1 or S1 ⊕ F1 and Ri = Si+1 or
Si+1 ⊕ Fi+1 for all 1 ≤ i < n. Moreover, Rn is a field. If n = 1, then either Γ(R) is
a single vertex or it is a path of length three. If n = 2, then R = S1 , R1 = S2 and
Γ(R) is an edge. If n ≥ 3, then since Γ(Rn−2 ) is a path, Γ(Rn−3 ) and hence Γ(R)
is Hamiltonian, which is a contradiction. The proof is complete.


Figure 1. (|I(R1 )|, |I(R2 )|) = (odd > 3, even > 3)

INTERSECTION GRAPH

7

Figure 2. (|I(R1 )|, |I(R2 )|) = (odd > 3, odd > 3)

Figure 3. (|I(R1 )|, |I(R2 )|) = (even > 3, even > 3)

Figure 4. (|I(R1 )|, |I(R2 )|) = (3, even ≥ 3)

Figure 5. (|I(R1 )|, |I(R2 )|) = (3, odd ≥ 3)
Theorem 3.2. Let R be an Artin ring. Then Γ(R) is Hamiltonian if and only if
it is pancyclic.
Proof. If Γ(R) is pancyclic, then clearly Γ(R) is Hamiltonian. Now, we show that
the converse is also true. Suppose on the contrary that there is an Artin ring R
such that Γ(R) is a non-pancyclic Hamiltonian graph and that R is minimal with
this property. If R is neither a local ring nor a direct sum of a local ring with
a field, then by applying the following transformations on the Hamiltonian cycles
constructed in cases 1 and 2 of Theorem 3.1, along with replacing horizontal or
vertical paths of length two to a path of length one, by joining its end vertices, we
would reach to cycles with possible arbitrary length ≥ 4.

8

A. AZIMI, A. ERFANIAN, M. FARROKHI D. G., AND N. HOSEINI

On the other hand, by Theorem 2.4, the graphs under consideration contain triangles, which implies that Γ(R) is pancyclic, a contradiction. Hence either R = S or
R = S × F , where (S, m) is a local ring and F is a field. If Γ(m) is Hamiltonian,
then either Γ(m) is pancyclic, which implies that Γ(R) is pancyclic too, contradicting the hypothesis, or Γ(m) is not pancyclic which contradicts the minimality of R.
Thus Γ(m) is not Hamiltonian and m is isomorphic to one of the five rings given in
Theorem 3.1. Now, a simple verification shows that in each case either Γ(m) is not
Hamiltonian or it is pancyclic, which is a contradiction. The proof is complete. 
References
[1] J. Bosak, The graphs of semigroups, Theory of Graphs and Application, Academic Press, New
York, 1964, 119–125.
[2] I. Chakrabarty, S. Ghosh, T. K. Mukherjee and M. K. Sen, Intersection graphs of ideals of
rings, Discrete Math. 309 (2009), 5381-5392.
[3] B. Csákéany and G. Pollák, The graph of subgroups of a finite group, Czech. Math. J. 19
(1969), 241–247.
[4] M. Herzog, P. Longobardi and M. Maj, On a graph related to the maximal subgroups of a
group, Bull. Aust. Math. Soc. 81 (2010), 317–328.
[5] S. H. Jafari and N. Jafari Rad, Domination in intersection graphs of rings and modules, Ital.
J. Pure Appl. Math. 28 (2011), 17–20.
[6] S. H. Jafari and N. Jafari Rad, Planarity of intersection graphs of ideals of rings, Int. Electron.
J. Algebra 8 (2010), 161–166.
[7] B. R. Macdonald, Finite Rings with Identity, Marcel Dekker, Inc., New York, 1974.
[8] T. A. McKee and F. R. McMorris, Topic in Intersection Graph Theory, SIAM, Philadelphia,
1999.
[9] R. Shen, Intersection graphs of subgroups of finite groups, Czech. Math. J. 135 (2010), 945–
950.
[10] B. Zelinka, Intersection graphs of finite abelian groups, Czech. Math. J. 25 (1975), 171–174.

Department of Pure Mathematics, Ferdowsi University of Mashhad, Mashhad, Iran
E-mail address: ali.azimi61@gmail.com
Department of Pure Mathematics, Ferdowsi University of Mashhad, Mashhad, Iran
E-mail address: erfanian@math.um.ac.ir
Department of Pure Mathematics, Ferdowsi University of Mashhad, Mashhad, Iran
E-mail address: m.farrokhi.d.g@gmail.com
Department of Pure Mathematics, Ferdowsi University of Mashhad, Mashhad, Iran
E-mail address: nesa.hoseini@gmail.com

