Order divisor graphs of finite groups
S. U. Rehman1 , A. Q. Baig1 , M. Imran 2 , and Z. U. Khan1

arXiv:1611.04280v3 [math.CO] 22 Jul 2017

1

Department of Mathematics,
COMSATS Institute of Information and Technology,
Attock, Pakistan.
2
Department of Mathematical Sciences,
United Arab Emirates University,
P.O. Box 15551, Al Ain, United Arab Emirates.
2
Department of Mathematics,
School of Natural Sciences(SNS),
National University of Sciences and Technology (NUST),
Sector H-12, Islamabad, Pakistan.
E-mail: {aqbaig1, imrandhab, zizu006}@gmail.com
shafiq ur rahman2@yahoo.com

Abstract. The interplay between groups and graphs have been the most
famous and productive area of algebraic graph theory. In this paper, we
introduce and study the graphs whose vertex set is group G such that
two distinct vertices a and b having different orders are adjacent provided
that o(a) divides o(b) or o(b) divides o(a).

2010 Mathematics Subject Classification: 05C25
Keywords: Finite groups, Cyclic groups, p-groups, Elementary abelian groups,
Connected Graphs, Star Graphs, Sequential Joins.

1

Introduction

All finite groups can be represented as the automorphism group of a connected
graph [4]. A graphical representation of group can be given by a set of generators
and relations. Given any group, symmetrical graphs known as Cayley graphs can
be generated, and these have properties related to the structure of the group [5].
Relating a graph to a group provides a method of visualizing a group and connects two important branches of mathematics. It gives a review of cyclic groups,
dihedral groups, direct products, generators and relations.
Groups are the main mathematical tools for studying symmetries of an object
and symmetries are usually related to graph automorphisms. Many structures in
abstract algebra are special cases of groups. Graph theory is one of the leading
research field in mathematics mainly because of its applications in diverse fields
which include biochemistry, electrical engineering, computer science and operations research. These both branches of mathematics are playing a vital role in

2

S. U. Rehman, A. Q. Baig, M. Imran, Z. U. Khan

modern mathematics. In group theory we study and analyze different groups and
their structures while in graph theory we focus on the graphs that denotes the
structure of materials and objects. The powerful combinatorial methods found
in graph theory have also been used to prove significant and well-known results
in a variety of areas in mathematics including group theory.
In the last few decades the researchers have focused on the modified form of
groups and graphs by inter relating their properties. The study of the algebraic
structures using the properties of graphs has become an inspiring research topic
in the last twenty years, leading to many fascinating results and questions, see
[2], [1], [7], and [8]. In this paper, we study a graph related to finite groups. We
call a graph an order divisor graph, denoted by OD(G), if its vertex set is a finite
group G and two distinct vertices a and b having different orders are adjacent
provided that o(a) divides o(b) or o(b) divides o(a).
For the reader’s convenience we give a working introduction here for the notions involved. A group G is called a p-group if every element of G has order a
power of p, where p is prime. The exponent of a group G is the smallest positive
integer m such that g m = e for all g ∈ G. An abelian group G is called an elementary abelin group or elementary abelin p-group if it is a p-group of exponent p for
some prime p, i.e., xp = e ∀ x ∈ G. A finite elementary abelin group is a group
that is isomorphic to Znp for some prime p and for some positive integer n. The
group of symmetries of a regular n-gon (n ≥ 3) is called a dihedral group or order
2n. The dihedral group has presentation Dn =< a, b | an = b2 = (ab)2 = e >. We
denote by U (Zn ), the group of units of Zn , i.e., U (Zn ) = {x̄ ∈ Zn | (x, n) = 1}.
For any two elements a, b of a group G, [a, b] denote the commutator a−1 b−1 ab.
If A, B are subsets of a group G then [A, B] =< [a, b] | a ∈ A, b ∈ B >. Particularly, [G, G] is called commutator subgroup denoted by G0 . A group G is called
nilpotent group if and only if it is the direct product of its Sylow subgroups, cf.
[6, Chapter 2, Section 3]. The unique maximal nilpotent normal subgroup of a
group G is called Fitting subgroup of G and is denoted by F (G), cf. [6, Chapter 6, Section 1]. A simple connected graph is an undirected graph without any
loops and multiple edges. A complete bipartite graph is a bipartite graph (i.e.,
a set of graph vertices decomposed into two disjoint sets such that no two graph
vertices within the same set are adjacent) such that every pair of graph vertices
in the two sets are adjacent. The star graph Sn of order n is a tree with one
vertex of degree n − 1 and all other vertices have degree 1, i.e., Sn ∼
= K1,n . We
denote by G1  G2  · · ·  Gk the sequential join of graphs G1 , G2 , ..., Gk , where
Gi  Gi+1 = Gi ∨ Gi+1 for all 1 ≤ i ≤ k − 1, i.e., by adding an edge from each
vertex of Gi to each vertex of Gi+1 , 1 ≤ i ≤ k − 1 The chromatic number χ(G)
of a graph G is defined to be the minimum number of colors required to color
the vertices of G, i.e., χ(G) = min{k : G is k − colorbale}.
In this paper we obtain the following results. The order divisor graph OD(G)
of a finite group G is a star graph if and only if every non-identity element of

Order divisor graphs of finite groups

3

G has prime order (Theorem 2.1). For an abelian group G, OD(G) is a star
graph if and onlyif G is elementary abelian (Corollary 2.1). The order divisor
graph OD U (Zn ) is a star graph Sφ(n) if and only if n | 24 (Corollary 2.2). The
order divisor graph OD(Zn ) is a star graph if and only if n is prime (Corollary
2.3). The order divisor graph OD(G) of a (finite) group G is a star graph if
and only if G is a p-group of exponent p, or a non-nilpotent group of order pa q,
or it is isomorphic to the simple group A5 (Corollary 2.4). The order divisor
graph of the dihedral group Dn (n ≥ 3) is a star graph S2n if and only if n
is prime (Theorem 2.2). If G is a finite p-group of order pn then OD(G) is a
complete multi-partite graph (Theorem 2.3). If G is a finite cyclic group of order
pn then OD(G) is complete (n + 1)-partite graph (Theorem 2.5). If G is a finite
cyclic group of order pn , then χ(OD(G)) = n + 1 (Corollary 2.6). If G is a cyclic
group of order p1 p2 , where p1 , p2 are distinct primes, then OD(G) is a sequential
join of graphs (Theorem 2.4). Similarly, if G is a cyclic group of order p1 p2 p3 ,
where p1 , p2 , p3 are distinct primes, then OD(G) is obtained by certain type of
sequential and cyclic joins. (Theorem 2.5). Let n ∈ N and let D be the set of
all (positive) divisors of n. Define a partial order  on D by a  b if and only
if a | b. Then (D, ) is a bounded lattice. We denote by Gn the comparability
graph on (D, ). In other words, Gn is a simple undirected graph with vertex
set D and two vertices a and b are adjacent if and only if a 6= b and either
a  b or b  a. The new extended graph is denoted by E(Gn ). Given a graph
G = (V, E), the reduced graph of G, denoted by R(G), is obtained from G by
merging those vertices which has same set of closed neighbors. Note that a closed
neighbor of v ∈ V is the set {u ∈ V |uv ∈ E} ∪ {v}. We obtain that if G is finite
group of order n, then G is cyclic if and only if E(Gn ) ∼
= OD(G) if and only if
Gn ∼
= R(OD(G)) (Theorem 2.6).
In this paper all the groups and graphs discussed are finite. We follow the
terminologies and notations of [5] for groups and [9] for graphs.

2

Main results

Definition 2.1. Let G be a finite group. Then OD(G) denotes the order divisor
graph whose vertex set is G such that two distinct vertices a and b having different
orders are adjacent provided that o(a) | o(b) or o(b) | o(a).
Remark 2.1. Some easy consequences of the definition are:
(i) OD(G) is a simple graphs, so there are no loops and multiple edges.
(ii) Since the identity element is the only element of a group having order one, so
the vertex associated to the identity element is adjacent to each vertex and
hence OD(G) is always a connected graph. Due to similar reason, if |G| > 2,
then OD(G) has diameter 2.
(iii) Since the vertex associated to the identity is adjacent to each vertex, therefore, if |G| > 3 then OD(G) is not a cycle. If |G| = 3 then G has two elements
of order 3 and the vertices associated to these two elements are not adjacent.
Hence OD(G) cannot be a cycle.

4

S. U. Rehman, A. Q. Baig, M. Imran, Z. U. Khan

(iv) If G is finite, then for every divisor d of |G|, the number of elements of order
d is a multiple of φ(d) (φ is Euler’s phi function). Hence, if |G| > 2, then
OD(G) cannot be a complete graph.
Theorem 2.1. The order divisor graph OD(G) is a star graph if and only if
every non-identity element of the group G has prime order.
Proof. Clearly, if every non-identity element of G has prime order, then OD(G)
is a star graph. Conversely, suppose that OD(G) is a star graph and x1 , x2 , ..., xn
are distinct non-identity elements of G with o(xi ) = di for 1 ≤ i ≤ n. As OD(G)
is a star graph, so di - dj for all i 6= j. If di is not prime for some i, then di has
a prime divisor, say p. But then by Cauchy’s theorem, G must have an element
of order p. Thus p = dj for some i 6= j, which is a contradiction. Hence each di
is prime.
Recall [6] that an elementary abelian group or elementary abelian p-group is
an abelian p-group of exponent p for some fixed prime p. A finite elementary
abelian group is a group that is isomorphic to Znp for some prime p and for some
positive integer n.
Corollary 2.1. Let G be an abelian group. Then OD(G) is a star graph if and
only if G is elementary abelian.
Proof. Suppose OD(G) is a star graph. Then by Theorem 2.1, every non-identity
element of G has prime order. Let a, b ∈ G such that o(a) and o(b) are distinct
primes. Since G is abelian, so o(ab) = o(a)o(b), which is a contradiction. Hence
G is an elementary abelian group (abelian p-group of exponent p for some prime
number p).
Remark 2.2. If the group G is not abelian, then above Corollary 2.1 fails. For
example, the order divisor graph OD(D3 ) of the dihedral group D3 =< a, b |
a3 = b2 = (ab)2 = e > is a star graph but D3 is not elementary abelian.

Fig. 1: OD(D3 ) ∼
= S6


Corollary 2.2. OD U (Zn ) is a star graph Sφ(n) if and only if n | 24.

Order divisor graphs of finite groups

5

∼ Sφ(n) , where φ is the Euler’s phi function. Then
Proof. Suppose OD(U (Zn )) =
by Corollary 2.1, U (Zn ) is an elementary abelian group (abelian p-group of
exponent p for some prime number p). Let φ(n) > 1, i.e., n > 2 (If φ(n) = 1,
then U (Zn ) is trivial). Then U (Zn ) has at least two elements that satisfy x2 = e.
Hence every non-identity element of U (Zn ) has order 2. Case 1: If n is odd. Then
2̄ ∈ U (Zn ) and so n | 22 − 1 = 3. Hence n = 1 or 3. Case 2: If n = 2t for some
t ≥ 1. Then 3̄ ∈ U (Zn ) and so n | 32 − 1 = 8. This implies n = 1, 2, 4 or 8.
Case 3: If n is any arbitrary positive integer. Then n = 2t k, where k is odd and
t is non-negative integer. Since U (Zn ) ∼
= U (Z2t ) × U (Zk ), so every non-identity
element of both U (Z2t ) and U (Zk ) has order 2. By above cases 1 and 2, we get
that 2t ∈ {1, 2, 4, 8} and k ∈ {1, 3}. Hence n = 2t k ∈ {1, 2, 4, 6, 8, 12, 24}.
Conversely, it is easy to check that if n | 24 then every non-identity element
of U (Zn ) has order 2, i.e., OD(U (Zn )) ∼
= Sφ(n) .
Corollary 2.3. OD(Zn ) is a star graph if and only if n is prime.
Recall [6] that for any two elements a, b of a group G, [a, b] denote the commutator a−1 b−1 ab. If A, B are subsets of a group G then [A, B] =< [a, b] | a ∈
A, b ∈ B >. Particularly, [G, G] is called commutator subgroup denoted by G0 .
A group G is called nilpotent group if and only if it is the direct product of its
Sylow subgroups. The unique maximal nilpotent normal subgroup of a group G
is called Fitting subgroup of G and is denoted by F (G).
Corollary 2.4. The order divisor graph OD(G) is a star graph if and only if
one of the following cases occur:
1. G is p-group of exponent p.
2. (a) |G| = pa q, 3 ≤ p < q, a ≥ 3, |F (G)| = pa−1 , |G : G0 | = p.
(b) |G| = pa q, 3 ≤ p < q, a ≥ 1, |F (G)| = |G0 | = pa .
(c) |G| = 2a p, p ≥ 3, a ≥ 2, |F (G)| = |G0 | = 2a .
(d) |G| = 2pa , p ≥ 3, a ≥ 1, |F (G)| = |G0 | = pa and F (G) is elementary
abelian.
3. G ∼
= A5 .
Proof. Apply [3, Main Theorem].
Theorem 2.2. The order divisor graph of the dihedral group Dn (n ≥ 3) is a
star graph S2n if and only if n is prime.
Proof. Dn =< a, b | an = b2 = (ab)2 = e >= {e, a, a2 , ..an−1 , b, ab, a2 b, ..., an−1 b}.
Suppose OD(Dn ) is a star graph. So, every pair of vertices corresponding to
non-identity elements is non-adjacent. Therefore, if o(ai ) 6= o(aj ) for some i, j ∈
n
for
{1, 2, 3...n−1}, then o(ai ) - o(aj ) and o(aj ) - o(ai ). Note that o(ak ) = gcd(k,n)
k
all k ∈ {1, 2, 3...n − 1}. Therefore, if o(a) 6= o(a ) for some k ∈ {1, 2, 3...n − 1},
then o(ak ) divides o(a) and so a and ak will become adjacent, which is not
possible. Hence o(a) = o(ak ) for all k ∈ {1, 2, 3...n − 1}. This implies that
gcd(k, n) = 1 for all k ∈ {1, 2, 3...n − 1}. Hence n is prime.
Conversely, Suppose that n is prime. Then o(ai ) = o(a) = n for all i ∈
{1, 2, 3...n − 1}. Moreover, o(ai b) = 2 for all i ∈ {1, 2, 3...n − 1}. Hence OD(Dn )
is a star graph.

6

S. U. Rehman, A. Q. Baig, M. Imran, Z. U. Khan

Theorem 2.3. Let G be a (finite) p-group of order pn . Then order divisor graph
OD(G) is a complete multi-partite graph.
Proof. Let p be a prime and Ai = {x ∈ G | o(x) = pi }. We can write G =
A0 ∪ A1 ∪ · · · ∪ An . It is not necessary that G has elements of order pi for
i > 1 and by Cauchy’s theorem, G must have element of order p. Therefore, for
some i > 1, Ai may be empty but A0 and A1 must be nonempty in the union
A0 ∪ A1 ∪ · · · ∪ An . Note that ab 6∈ E(OD(G)) if a, b ∈ Ai for some 0 ≤ i ≤ n.
Suppose a ∈ Ai and b ∈ Aj , where i 6= j. Then o(a) = pi and o(b) = pj . If
i < j then pi strictly divides pj and if i > j then pj strictly divides pi . Therefore
ab ∈ E(OD(G)) and hence OD(G) is complete multipartite graph.
Example 2.1.

Fig. 2: OD(D4 )
The line joining two independent sets of vertices means that each vertex in one
independent set is adjacent to each vertex of other independent set.

Corollary 2.5. Let G be a finite cyclic group of order pn . Then OD(G) is
isomorphic to the complete (n+1)-partite graph K1,p−1,p(p−1),p2 (p−1),...,pn−1 (p−1) .
Proof. Let Ai = {x ∈ G : o(x) = pi }. We can write G = A0 ∪ A1 ∪ · · · ∪ An .
Since G is cyclic, so by [5, Theorem 4.4], |Ai | = φ(pi ) = pi−1 (p − 1), where φ is
Euler’s phi function. Note that ab 6∈ E(OD(G)) if a, b ∈ Ai for any 0 ≤ i ≤ n.
Suppose a ∈ Ai and b ∈ Aj , where i 6= j. Then o(a) = pi and o(b) = pj . If
i < j then pi strictly divides pj and if i > j then pj strictly divides pi . Therefore
ab ∈ E(OD(G)) and hence OD(G) is isomorphic to the complete (n + 1)-partite
graph K1,p−1,p(p−1),p2 (p−1),...,pn−1 (p−1) .

Corollary 2.6. If G is a finite cyclic group of order pn , then χ(OD(G)) = n+1.
Example 2.2. The order divisor graph OD(Z8 ) is shown below.

Order divisor graphs of finite groups

7

Fig. 3: OD(Z8 )
The line joining two independent sets of vertices means that each vertex in one
independent set is adjacent to each vertex of other independent set.

We denote by G1  G2  · · ·  Gk the sequential join of graphs G1 , G2 , ..., Gk ,
where Gi  Gi+1 = Gi ∨ Gi+1 for all 1 ≤ i ≤ k − 1, i.e., by adding an edge from
each vertex of Gi to each vertex of Gi+1 , 1 ≤ i ≤ k − 1.
Theorem 2.4. Let G be a cyclic group of order p1 p2 , where p1 , p2 are distinct
primes. Then OD(G) is a sequential join (G1  G2  G3 )  K1 , where G1 ∼
=
(p1 − 1)K1 , G2 ∼
= (p1 − 1)(p2 − 1)K1 and G3 ∼
= (p2 − 1)K1 .
Proof. The divisors of p1 p2 are 1, p1 , p2 , p1 p2 . We make a partition of the vertex
set G as G = Ap1 ∪ Ap1 p2 ∪ Ap2 ∪ A1 , where Ap1 = {x ∈ G : o(x) = p1 }, Ap1 p2 =
{x ∈ G : o(x) = p1 p2 }, Ap2 = {x ∈ G : o(x) = p2 } and A1 = {x ∈ G : o(x) = 1}.
By [5, Theorem 4.4], |Ap1 | = φ(p1 ) = p1 −1, |Ap1 p2 | = φ(p1 p2 ) = (p1 −1)(p2 −1),
|Ap2 | = φ(p2 ) = (p2 − 1) and |A1 | = 1, where φ is the Euler’s phi function. Since
p1 strictly divides p1 p2 , so each vertex in Ap1 is adjacent to each vertex in Ap1 p2 .
Similarly, as p2 strictly divides p1 p2 , so each vertex in Ap2 is adjacent to each
vertex in Ap1 p2 . Note that p1 - p2 and p2 - p1 , so no vertex of Ap1 is adjacent
to any vertex of Ap2 and no vertex of Ap2 is adjacent to any vertex of Ap1 .
Clearly, the single vertex in A1 , i.e corresponding to the identity element of G,
is adjacent to every vertex in Ap1 , every element in Ap1 p2 and every element in
Ap2 . Also note that the vertices in Ap1 , Ap1 p2 and Ap2 are independent. Hence
OD(G) = (G1 + G2 + G3 ) + K1 , where G1 ∼
= (p1 − 1)K1 , G2 ∼
= (p1 − 1)(p2 − 1)K1
∼
and G3 = (p2 − 1)K1 .

Example 2.3.

8

S. U. Rehman, A. Q. Baig, M. Imran, Z. U. Khan

Fig. 4: OD(Z15 )
The line joining two independent sets of vertices means that each vertex in one
independent set is adjacent to each vertex of other independent set.

We denote by G1  G2  · · ·  Gk the sequential join of graphs G1 , G2 , ..., Gk ,
where Gi  Gi+1 = Gi ∨ Gi+1 for all 1 ≤ i ≤ k − 1, i.e., by adding an edge from
each vertex of Gi to each vertex of Gi+1 , 1 ≤ i ≤ k − 1.
Theorem 2.5. Let H be a cyclic group of order p1 p2 p3 , where p1 , p2 and p3 are
distinct primes. Then OD(H) is defined as:




(G1 G12 )∪(G12 G2 )∪(G2 G23 )∪(G23 G3 )∪(G3 G13 )∪(G13 G1 ) G123 K1

where Gi ∼
= (pi − 1)K1 , 1 ≤ i ≤ 3, G12 ∼
= (p1 − 1)(p2 − 1)K1 , G23 ∼
= (p2 − 1)(p3 −
∼
1)K1 , G13 ∼
(p
−
1)(p
−
1)K
,
and
G
(p
−
1)(p
−
1)(p
= 1
3
1
123 =
1
2
3 − 1)K1 .

Proof. Let H be a cyclic group such that |H| = p1 p2 p3 , where p1 , p2 and p3 are
distinct primes. The divisors of p1 p2 p3 are 1, p1 , p2 , p3 , p1 p2 , p1 p3 , p2 p3 , p1 p2 p3 .
We make a partition of the vertex set H, based on the divisors of p1 p2 p3 , as
follows: H = Ap1 ∪Ap1 p2 ∪Ap1 p3 ∪Ap2 ∪Ap2 p3 ∪Ap3 ∪Ap1 p2 p3 ∪A1 , where Ai = {x ∈
H | o(x) = i} for i ∈ {1, p1 , p2 , p3 , p1 p2 , p1 p3 , p2 p3 , p1 p2 p3 }. By [5, Theorem 4.4],
|Ap1 | = φ(p1 ) = p1 − 1, |Ap1 p2 | = φ(p1 p2 ) = (p1 − 1)(p2 − 1), |Ap1 p3 | = φ(p1 p3 ) =
(p1 − 1)(p3 − 1),|Ap2 | = φ(p2 ) = (p2 − 1), |Ap2 p3 | = φ(p2 p3 ) = (p2 − 1)(p3 − 1),
|Ap3 | = φ(p3 ) = (p3 − 1), |Ap1 p2 p3 | = φ(p1 p2 p3 ) = (p1 − 1)(p2 − 1)(p3 − 1) and
|A1 | = 1, where φ is the Euler’s phi function. Since p1 strictly divides p1 p2 , p1 p3
and p1 p2 p3 , so each vertex in Ap1 is adjacent to each vertex in Ap1 p2 , Ap1 p3 and
Ap1 p2 p3 . As p2 strictly divides p1 p2 , p2 p3 and p1 p2 p3 , so each vertex in Ap2 is
adjacent to each vertex in Ap1 p2 , Ap2 p3 and Ap1 p2 p3 . Similarly p3 strictly divides
p1 p3 , p2 p3 and p1 p2 p3 , so each vertex in Ap3 is adjacent to each vertex in Ap1 p3 ,
Ap2 p3 and Ap1 p2 p3 . Note that p1 - p2 , p3 , p2 - p1 , p3 and p3 - p1 , p2 , so no vertex
of Ap1 is adjacent to any vertex of Ap2 or Ap3 , no vertex of Ap2 is adjacent to
any vertex of Ap1 or Ap3 and similarly no vertex of Ap3 is adjacent to any vertex
of Ap1 or Ap2 . Clearly, the single vertex in A1 , i.e., corresponding to the identity
element of H, is adjacent to every vertex in Ap1 , Ap2 , Ap3 , every vertex in Ap1 p2 ,
Ap1 p3 , Ap2 p3 and every vertex in Ap1 p2 p3 . Also note that the sets of vertices Ap1 ,
Ap2 , Ap3 , Ap1 p2 , Ap1 p3 , Ap2 p3 and Ap1 p2 p3 are independent sets. Hence OD(H)

Order divisor graphs of finite groups

9


is defined as
(G1  G12 ) ∪ (G12  G2 ) ∪ (G2  G23 ) ∪ (G23  G3 ) ∪ (G3  G13 ) ∪


(G13  G1 )  G123  K1 .

Example 2.4.

Fig. 5: OD(Z30 )
The line joining two independent sets of vertices means that each vertex in one
independent set is adjacent to each vertex of other independent set.

Definition 2.2. Let n ∈ N and let D be the set of all (positive) divisors of n.
Define a partial order  on D by a  b if and only if a | b. Then (D, ) is a
bounded lattice. We denote by Gn the comparability graph on (D, ). In other
words, Gn is a simple undirected graph with vertex set D and two vertices a and
b are adjacent if and only if a 6= b and either a  b or b  a. We denote by
E(Gn ) the extended graph of Gn which is obtained by replacing each vertex d in
Gn by φ(d) copies of d which form an independent set.
Definition 2.3. Given a graph G = (V, E), the reduced graph of G, denoted by
R(G), is obtained from G by merging those vertices which has same set of closed
neighbors, where a closed neighbor of v ∈ V is the set {u ∈ V |uv ∈ E} ∪ {v}.
Theorem 2.6. Let G be a finite group of order n. The following are equivalent:
(a) G is cyclic;
(b) E(Gn ) ∼
= OD(G);
(c) Gn ∼
R(OD(G)).
=

10

S. U. Rehman, A. Q. Baig, M. Imran, Z. U. Khan

Proof. (a) ⇔ (b): Let D be the set of all (positive) divisors of n. Suppose G is
cyclic. Then for each d ∈ D, G has exactly φ(d) elements of order d, cf. [5, Theorem 4.4]. Hence by definitions of OD(G) and Gn , we get that E(Gn ) ∼
= OD(G).
Conversely, suppose E(Gn ) ∼
= OD(G). Since n ∈ D, so Gn has a vertex associated to n and hence E(Gn ) has φ(n) vertices associated to the group elements
of order n. Hence G is cyclic.
(a) ⇔ (c): Let D be the set of all distinct (positive) divisors of n. Suppose
G is cyclic. Then for each d ∈ D, G has exactly φ(d) elements of order d, cf. [5,
Theorem 4.4]. Therefore, by definitions, Gn is isomorphic to the reduced graph of
OD(G). Conversely, let Gn ∼
= R(OD(G)). Since, OD(G) consists of independent
sets associated to elements of same order in G and by reducing OD(G) we obtain
the comparability graph Gn (in Gn we have a vertex associated to each divisor
of n), therefore in OD(G) we have independent set of vertices associated to each
divisor of |G| = n. In particular, G must have elements or order n. Hence G is
cyclic.
Remark 2.3. We saw that for finite cyclic groups G, the comparability graph
Gn can be studied by passing to the order divisor graph OD(G). Also the order
divisor graph OD(G) can be studied by passing to the comparability graph Gn .
That is, we have maps
E
{Comparability graphs}

{Order divisor graphs}
R

References
1. A. Ballester-Bolinches and J. Cossey, Graphs and classes of finite groups, Note di
Matematica, 33(1)(2013), 89-94.
2. P. J. Cameron and S. Ghosh, The power graph of a finite group, Discrete Mathematics, 311(2011), 1220-1222.
3. M. Deaconescu, Classification of finite groups with all elements of prime order,
Proc. Amer. Math. Soc. 106(3)(1989), 625-629.
4. R. Frucht, Graphs of Degree 3 with given abstract group, Canad. J. Math., 1
(1949), 365-378.
5. J. A. Gallians, Contemporary Abstract Algebra, 8th edition, Brooks/Cole, 2013.
6. D. Gorenstein, Finite groups, Harper and Row, 1968.
7. Z. Raza, Commuting graphs of dihedral type groups, Applied Mathematics ENotes, 13(2013), 221-227.
8. S. U. Rehman, Comaximal factorization graphs in integral domains, Journal of
Prime Research in Mathematics, 9(2013), 65-71.
9. D. B. West, Introduction to Graph Theory, Prentice Hall. Inc. Upper Saddle River,
NJ, 1996.

