Planar, outerplanar and ring graph

arXiv:1712.06993v1 [math.AC] 17 Dec 2017

of the intersection graph

∗

S. Khojasteh

Department of Mathematics, Lahijan Branch, Islamic Azad University, Lahijan, Iran
s khojasteh@liau.ac.ir

Abstract
Let m, n > 1 be two integers, and Zn be a Zm -module. Let I(Zm )∗ be the set of all
non- zero proper ideals of Zm . The Zn -intersection graph of Zm , denoted by Gn (Zm )
is a graph with the vertex set I(Zm )∗ , and two distinct vertices I and J are adjacent
if and only if IZn ∩ JZn 6= 0. In this paper, we determine the values of m and n for
which Gn (Zm ) is planar, outerplanar or ring graph.

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], [6]
and [13]. Also the intersection graphs of some algebraic structures such as groups, rings
and modules have been studied by several authors, see [3, 4, 8, 9]. In [8], 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 [4], 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 distinct vertices are adjacent if and only if they have non-zero intersection. In [11],
the M intersection graph of ideals of R denoted by GM (R), is defined to be the graph
with the vertex set I(R)∗ , and two distinct vertices I and J are adjacent if and only
∗

Key words: intersection graph, ring graph, planarity, outerplanarity.
2010 Mathematics Subject Classification: 05C10, 05C25, 13A15.

1

if IM ∩ JM 6= 0. Also, the Zn intersection graph of Zm , Gn (Zm ) was studied in [12],
where n, m > 1 are integers and Zn is a Zm -module. 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). If {a, b} ∈ E(G), we say a is adjacent to b and
write a — b. If |V (G)| ≥ 2, then a path from a to b is a series of adjacent vertices a — x1
— x2 — · · · — xn — b. For a, b ∈ V (G) with a 6= b, d(a, b) denotes the length of a shortest
path from a to b. If there is no such path, then we define d(a, b) = ∞. We say that G is
connected if there is a path between any two distinct vertices of G. A cycle is a path that
begins and ends at the same vertex in which no edge is repeated and all vertices other
than the starting and ending vertex are distinct. We denote the complete graph of order
n by Kn . A graph is bipartite if its vertices can be partitioned into two disjoint subsets A
and B such that each edge connects a vertex from A to one from B. A bipartite graph is
a complete bipartite graph if every vertex in A is adjacent to every vertex in B. We denote
the complete bipartite graph, with part sizes m and n by Km,n . The disjoint union of
graphs G1 and G2 , which is denoted by G1 ∪ G2 , where G1 and G2 are two vertex-disjoint
graphs, is a graph with V (G1 ∪ G2 ) = V (G1 ) ∪ V (G2 ) and E(G1 ∪ G2 ) = E(G1 ) ∪ E(G2 ).
A graph G may be expressed uniquely as a disjoint union of connected graphs. These
graphs are called the connected components, or simply the components, of G. Recall that
a graph is said to be planar if it can be drawn in the plane so that its edges intersect only
at their ends. A subdivision of a graph is any graph that can be obtained from the original
graph by replacing edges by paths.
In [12], the authors were mainly interested in the study of Zn intersection graph of
ideals of Zm . For instance, they determined the values of m for which Gn (Zm ) is connected,
complete, Eulerian or has a cycle. In this article, we determine all integer numbers n and
m for which Gn (Zm ) is planar, outerplanar or ring graph.

2

Results

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 ′ =
2

{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
Q
b). It is easy to see that I(Zm ) = {dZm : d divides m} and |I(Zm )∗ | = si=1 (αi + 1) − 2.
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 ].
In this section, we study the planarity of Gn (Zm ). A remarkable simple characterization of the planar graphs was given by Kuratowski in 1930.
Theorem A. [7, Theorem 10.30] (Kuratowski’s Theorem) A graph is planar if and only
if it contains no subdivision of either K5 or K3,3 .
Theorem 1. Let Zn be a Zm -module. Then Gn (Zm ) is planar if and only if one of the
following holds:
(1) m = pα1 1 , n = pβ1 1 and β1 ≤ 5.
(2) m = pα1 1 pα2 2 , n = p1 and α2 ≤ 4.
(3) m = pα1 1 p2 , n = p21 .
(4) m = pα1 1 p2 p3 , n = p1 .
(5) m = p1 pα2 2 , n = p1 p22 and α2 = 2, 3, 4.
(6) m = p1 p2 p3 , n = p1 p2 .
(7) m = pα1 1 pα2 2 , n = p1 p2 and α1 , α2 ≤ 4.
(8) m = n = p1 p2 p3 .
Proof. One side is obvious. For the other side assume that Gn (Zm ) is planar. With
β′

no loss of generality assume that n = pβ1 1 . . . ps′s , where 1 ≤ s′ ≤ s and βi 6= 0, for
i = 1, . . . , s′ . We note that s′ ≤ 3. Since otherwise, p1 Zm , p2 Zm , p3 Zm , p4 Zm , p1 p2 Zm
forms a K5 , a contradiction. Consider three following cases:
Case 1. s′ = 1. If β1 ≥ 6, then p1 Zm , p21 Zm , p31 Zm , p41 Zm , p51 Zm forms a K5 , a
contradiction. Hence β1 ≤ 5. If s ≥ 4, then p2 Zm , p3 Zm , p4 Zm , p2 p3 Zm , p2 p4 Zm forms
a K5 , a contradiction. Therefore s ≤ 3. There are three following subcases:
Subcase 1. s = 1. Clearly, Gpβ1 (Zpα1 ) is planar, where β1 ≤ 5. Therefore (1) holds.
1

1

Subcase 2. s = 2. We note that α2 ≤ 4. Otherwise, p2 Zm , p22 Zm , p32 Zm , p42 Zm , p52 Zm
3

forms a K5 , a contradiction. If β1 ≥ 3, then p1 Zm , p21 Zm , p2 Zm , p1 p2 Zm , p21 p2 Zm forms a
K5 , a contradiction. This implies that β1 = 1, 2. If β1 = 1, then it is easy to check that
Gp1 (Zpα1 pα2 ) is planar, where α2 ≤ 4. Therefore (2) holds. Now, let β1 = 2. If α2 ≥ 2,
1

2

then p1 Zm , p2 Zm , p1 p2 Zm , p22 Zm , p1 p22 Zm forms a K5 , a contradiction. Therefore α2 = 1.
Obviously, Gp21 (Zpα1 p2 ) is planar and (3) holds.
1

Subcase 3. s = 3. If α2 ≥ 2, then p2 Zm , p3 Zm , p22 Zm , p2 p3 Zm , p22 p3 Zm forms a
K5 , a contradiction. Hence α2 = 1. Similarly, we find that α3 = 1. If β1 ≥ 2, then
p1 Zm , p2 Zm , p3 Zm , p1 p2 Zm , p2 p3 Zm forms a K5 , a contradiction. It is easy to see that
Gp1 (Zpα1 p2 p3 ) is planar and (4) holds.
1

Case 2. s′ = 2. If β1 , β2 ≥ 2, then p1 Zm , p21 Zm , p2 Zm , p1 p2 Zm , p21 p2 Zm forms a K5 , a
contradiction. Hence with no loss of generality we may assume that β1 = 1.
First assume that β2 ≥ 2. If α1 ≥ 2, then p1 Zm , p21 Zm , p2 Zm , p1 p2 Zm , p21 p2 Zm forms
a K5 , a contradiction. Therefore α1 = 1. If s ≥ 3, then p1 Zm , p2 Zm , p1 p2 Zm , p3 Zm , p1 p3 Zm
forms a K5 , a contradiction. Thus s = 2. If β2 ≥ 3, then p1 Zm , p2 Zm , p22 Zm , p1 p2 Zm , p1 p22 Zm
forms a K5 , a contradiction. Therefore β2 = 2. If α2 ≥ 5, then p2 Zm , p22 Zm , p32 Zm , p42 Zm ,
p52 Zm forms a K5 , a contradiction. Therefore α2 ≤ 4. It is easy to see that Gp1 p22 (Zp1 pα2 )
2

is planar, where α2 = 2, 3, 4 and (5) holds.
Now, assume that β2 = 1. Let s ≥ 3. If α3 ≥ 2, then p1 Zm , p3 Zm , p23 Zm , p1 p3 Zm , p1 p23 Zm
forms a K5 , a contradiction. Hence α3 = 1. If α1 ≥ 2, then p1 Zm , p21 Zm , p3 Zm , p1 p3 Zm ,
p21 p3 Zm forms a K5 , a contradiction. Therefore α1 = 1 and similarly, α2 = 1. It is clear
that Gp1 p2 (Zp1 p2 p3 ) is planar and (6) holds. Now, assume that s = 2. Then we find that
α1 , α2 ≤ 4. Also, one can easily check that Gp1 p2 (Zpα1 pα2 ) is planar, where α1 , α2 ≤ 4.
1

2

Therefore (7) holds.
Case 3. s′ = 3. If s ≥ 4, then p1 Zm , p2 Zm , p3 Zm , p4 Zm , p1 p4 Zm forms a K5 , a
contradiction. Therefore s = 3. If α1 ≥ 3, then p1 Zm , p21 Zm , p31 Zm , p2 Zm , p3 Zm forms
a K5 , a contradiction. Therefore α1 ≤ 2 and similarly α2 , α3 ≤ 2. If β1 ≥ 2, then
p1 Zm , p2 Zm , p3 Zm , p1 p2 Zm , p1 p3 Zm forms a K5 , a contradiction. Therefore β1 = 1 and
similarly we have β2 = β3 = 1. If α1 = α2 = 2, then p1 Zm , p21 Zm , p2 Zm , p22 Zm , p1 p2 Zm
forms a K5 , a contradiction. Therefore α1 = 1 or α2 = 1. With no loss of generality,
we may assume that α1 = 1. By The same argument as we saw we find that α2 = 1 or
α3 = 1. Thus we have α1 = α2 = α3 = 1 or α1 = α2 = 1 and α3 = 2. It is clear that if
α1 = α2 = α3 = 1, then Gn (Zm ) is planar. Therefore (8) holds. Also, Gp1 p2 p3 (Zp1 p2 p23 ) is
not planar because p3 Zm , p23 Zm , p2 p3 Zm , p2 p23 Zm , p2 Zm forms a K5 which is impossible. 

4

Corollary 1. Let m be a positive integer number. Then G(Zm ) is planar if and only if
m ∈ {p1 , p21 , p31 , p41 , p51 , p1 p2 , p1 p22 , p1 p2 p3 }.
Let G be a graph with n vertices and m edges. We recall that a chord is any edge of G
joining two nonadjacent vertices in a cycle of G. Let C be a cycle of G. We say C is
a primitive cycle if it has no chords. Also, a graph G has the primitive cycle property
(PCP) if any two primitive cycles intersect in at most one edge. The number f rank(G) is
called the free rank of G and it is the number of primitive cycles of G. Also, the number
rank(G) = m − n + r is called the cycle rank of G, where r is the number of connected
components of G. The cycle rank of G can be expressed as the dimension of the cycle
space of G. By [10, Proposition 2.2], we have rank(G) ≤ f rank(G). A graph G is called
a ring graph if it satisfies in one of the following equivalent conditions (see [10, Theorem
2.13]).
(i) rank(G) = f rank(G),
(ii) G satisfies the PCP and G does not contain a subdivision of K4 as a subgraph.
Also, an undirected graph is an outerplanar graph if it can be drawn in the plane without
crossings in such a way that all of the vertices belong to the unbounded face of the drawing.
There is a characterization for outerplanar graphs that says a graph is outerplanar if and
only if it does not contain a subdivision of K4 or K2,3 . By [10, Proposition 2.17], we find
that every outerplanar graph is a ring graph and every ring graph is a planar graph.
Example 1. In Fig.1, let v1 = p2 Zp1 p22 , v2 = p1 p2 Zp1 p22 , v3 = p22 Zp1 p22 , v4 = p1 Zp1 p22 . Also,
in Fig.2, assume that v1 = p1 p2 Zp1 p32 , v2 = p1 p22 Zp1 p32 , v3 = p22 Zp1p32 , v4 = p1 Zp1 p32 , v5 =
p2 Zp1 p32 , v6 = p32 Zp1 p32
v1

v2

v1

v2

v3

v3

v4

v4

v5

v6

Fig.1 G(Zp1 p22 )

Fig.2 Gp1 p22 (Zp1 p32 )

Example 2. In Fig.3, let v1 = p1 Zp1 p2 p3 , v2 = p1 p2 Zp1 p2 p3 , v3 = p2 Zp1 p2 p3 , v4 = p1 p3 Zp1 p2 p3 , v5 =
p3 Zp1 p2 p3 , v6 = p2 p3 Zp1p2 p3 . In Fig.4, let v1 = p1 p2 Zp1 p2 p3 , v2 = p1 Zp1p2 p3 , v3 = p1 p3 Zp1 p2 p3 , v4 =
p 2 Z p 1 p 2 p 3 , v5 = p 3 Z p 1 p 2 p 3 , v6 = p 2 p 3 Z p 1 p 2 p 3 .

5

v1

v1

v2

v3

v4

v5

v6

v2

v4

v3

v5

v6

Fig.3 Gp1 p2 (Zp1 p2 p3 )

Fig.4 G(Zp1 p2 p3 )

Example 3. In Fig.5, let v1 = p2 Zp1 p32 , v2 = p22 Zp1 p32 , v3 = p32 Zp1 p32 , v4 = p1 p2 Zp1 p32 , v5 =
p1 Zp1 p32 , v6 = p1 p22 Zp1p32 .
v1

v2

v4

v3

v5

v6

Fig.5 Gp1 p2 (Zp1 p32 )
Theorem 2. Let Zn be a Zm -module. Then Gn (Zm ) is a ring graph if and only if one of
the following holds:
(1) m = pα1 1 , n = pβ1 1 and β1 ≤ 4.
(2) m = pα1 1 pα2 2 , n = p1 and α2 ≤ 3.
(3) m = pα1 1 p2 , n = p21 .
(4) m = pα1 1 p2 p3 , n = p1 .
(5) m = p1 pα2 2 , n = p1 p22 and α2 = 2, 3.
(6) m = p1 p2 p3 , n = p1 p2 .
(7) m = pα1 1 pα2 2 , n = p1 p2 and α1 , α2 ≤ 3.
(8) m = n = p1 p2 p3 .
6

Proof. One side is obvious. For the other side assume that Gn (Zm ) is a ring graph.
Then it is planar and by Theorem 1, we have eight following cases:
Case 1. m = pα1 1 , n = pβ1 1 and β1 ≤ 5. If β1 = 5, then p1 Zm , p21 Zm , p31 Zm , p41 Zm forms
a K4 , a contradiction. Therefore β1 ≤ 4. It is easy to check that Gn (Zm ) is a ring graph
and (1) holds.
Case 2. m = pα1 1 pα2 2 , n = p1 and α2 ≤ 4. Clearly, if α2 = 4, then p2 Zm , p22 Zm , p32 Zm ,
p42 Zm forms a K4 , a contradiction. Hence α2 ≤ 3. Now, Gn (Zm ) has at most three
non-isolated vertices and so it is a ring graph and (2) holds.
Case 3. m = pα1 1 p2 , n = p21 . In this case, {p1 Zm , p2 Zm , p1 p2 Zm } is the set of all
non-isolated vertices of Gn (Zm ). This yields that Gn (Zm ) is a ring graph and (3) holds.
Case 4. m = pα1 1 p2 p3 , n = p1 . It is easy to see that Gp1 (Zpα1 p2 p3 ) is a ring graph and
1

(4) holds.
Case 5. m = p1 pα2 2 , n = p1 p22 and α2 = 2, 3, 4. If α2 = 4, then p2 Zm , p22 Zm , p32 Zm , p42 Zm
forms a K4 , a contradiction. Therefore α2 = 2, 3. By Fig.1 and Fig.2, Gp1 p22 (Zp1 p22 ) and
Gp1 p22 (Zp1 p32 ) are ring graphs and (5) holds.
Case 6. m = p1 p2 p3 , n = p1 p2 . In this case, by Fig.3, we conclude that Gn (Zm ) is a
ring graph and (6) holds.
Case 7. m = pα1 1 pα2 2 , n = p1 p2 and α1 , α2 ≤ 4. If α1 = 4, then p1 Zm , p21 Zm , p31 Zm , p41 Zm
forms a K4 , a contradiction. Hence α1 ≤ 3 and similarly, α2 ≤ 3. Now, by [12, Theorem
11], we have Gn (Zm ) \ A ∼
= Kα ∪ Kα , where A is the set of all non-isolated vertices of
1

2

Gn (Zm ). Therefore (7) holds.(see Fig.5)
Case 8. m = n = p1 p2 p3 . By Fig.4, we find that Gn (Zm ) is a ring graph and (8)
holds.



Corollary 2. Let m be a positive integer number. Then G(Zm ) is a ring graph if and
only if m ∈ {p1 , p21 , p31 , p41 , p1 p2 , p1 p22 , p1 p2 p3 }.
Using theorems in this section and the proof of pervious theorem, we have the following
result.
Theorem 3. Let Zn be a Zm -module. Then Gn (Zm ) is outerplanar if and only if one of
the following holds:

7

(1) m = pα1 1 , n = pβ1 1 and β1 ≤ 4.
(2) m = pα1 1 pα2 2 , n = p1 and α2 ≤ 3.
(3) m = pα1 1 p2 , n = p21 .
(4) m = pα1 1 p2 p3 , n = p1 .
(5) m = p1 pα2 2 , n = p1 p22 and α2 = 2, 3.
(6) m = p1 p2 p3 , n = p1 p2 .
(7) m = pα1 1 pα2 2 , n = p1 p2 and α1 , α2 ≤ 3.
(8) m = n = p1 p2 p3 .
Also, we have the following corollary.
Corollary 3. Let m be a positive integer number. Then G(Zm ) is outerplanar if and only
if m ∈ {p1 , p21 , p31 , p41 , p1 p2 , p1 p22 , p1 p2 p3 }.

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.
[3] S. Akbari, R. Nikandish, M.J. Nikmehr, Some results on the intersection graphs of
ideals of rings, Journal of Algebra and Its Applications 12 (4) (2013), Article No.
1250200.
[4] S. Akbari, H.A. Tavallaee, S. Khalashi Ghezelahmad, Intersection graph of submodules of a module, Journal of Algebra and Its Applications 11 (1) (2012), Article No.
1250019.
[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.
8

[7] J.A. Bondy, U.S.R. Murty, Graph Theory, Graduate Texts in Mathematics 244,
Springer, New York, 2008.
[8] I. Chakrabarty, S. Ghosh, T.K. Mukherjee, M.K. Sen, Intersection graphs of ideals
of rings, Discrete Mathematics, 309 (2009), 5381–5392
[9] B. Csákány and G. Pollák, The graph of subgroups of a finite group (Russian),
Czech. Math. J. 19 (1969), 241–247.
[10] I. Gitler, E. Reyes, R. H. Villarreal, Ring graphs and complete intersection toric
ideals, Discrete Math. 310(3), (2010) 430-441.
[11] F. Heydari, On the intersection graph of ideals of a commutative ring,
arXiv:1702.08525(2017).
[12] S. Khojasteh, On the intersection graph of ideals of Zm , arXiv:1703.01150(2017).
[13] M. J. Nikmehr, F. Heydari, The M-principal graph of a commutative ring, Period.
Math. Hungar. 68 (2) (2014), 185–192.

9

