ON NON-CYCLIC GRAPH OF A GROUP

arXiv:1609.07247v2 [] 9 Jan 2017

E. VATANDOOST AND Y. GOLKHANDYPOUR
Abstract. Here we study some algebraic propertices of non-cyclic graphs.
In this paper we show that ΓG is isomorphic to K3 ∪ (n − 4)K1 or K4 ∪
(n − 5)K1 if and only if G is isomorphic to D8 or D10 , respectively. We
characterize all groups of order n like G in which γ(ΓG ) + γ(ΓG ) ∈ {n, n −
1, n − 2, n − 3}, where |Cyc(G)| = 1.

1. Introduction
The study of algebraic structures, using the properties of graphs, becomes
an exciting research topic in the last twenty years, leading to many fascinating
results and questions. There are many papers on assigning a graph to a ring
or group and investigation of algebraic properties of ring or group using the
associated graphs.
Before starting let us introduce some necessary notation and definitions. Let
Γ = (V, E) be a simple graph. A graph Γ is said to be connected if each pair
of vertices are joined by a walk. The number of edges of the shortest walk
joining v and u is called the distance between v and u and denoted by d(u, v).
The maximum value of the distance function in a connected graph Γ is called
the diameter of Γ and denoted by diam(Γ). The degree of a vertex v ∈ V (Γ)
is the number of edges which are adjacent to v in Γ and denoted by degΓ (v).
A universal vertex is a vertex that is adjacent to every other vertices in the
graph. The maximum degree of a graph Γ denoted by ∆(Γ), and the minimum
degree of a graph Γ denoted by δ(Γ), are the maximum and minimum degree
of its vertices.
A dominating set for Γ is a subset D of V (Γ) such that every vertex not in
D is adjacent to at least one vertex of D. The domination number of Γ is the
number of vertices in a smallest dominating set for Γ and denoted by γ(Γ).
See [5], [10] and [12] for more details.
Let G be a non-locally cyclic group and let Z(G) denoted the centralizer of
1991 Mathematics Subject Classification. Algebraic combinatorics: 05Exx, Graph theory: 05Cxx.
Key words and phrases. Finite group, Acceptable group, Non-cyclic graph, Domination
number.
* We thank Professor Saeed Akbari for his comments and expert of our paper.
1

2

E. VATANDOOST AND Y. GOLKHANDYPOUR

G. If x ∈ G, then CycG (x) denotes the cyclicizer of x in G and defined by
CycG (x) = {y ∈ G | hx, yi is cyclic}.
The cyclicizer of G denoted by Cyc(G) such that
Cyc(G) = {y ∈ G | hx, yi is cyclic f or all x ∈ G}.
It is a simple fact that for any group G, Cyc(G) is a locally cyclic subgroup of
G. Also in general for an element x of a group G, CycG (x) is not a subgroup
of G. Also for each x ∈ G, CG (x) is used for the centralizer of x.
In this paper, we study some graph properties of the non-cyclic graph ΓG of
non-locally cyclic group G. Let G be a non-locally cyclic group of order n. The
non-cyclic graph of G, denoted by ΓG , is a graph with vertex set G \ Cyc(G)
and two vertices x and y are adjacent if and only if hx, yi is not cyclic. Also the
complement of non-cyclic graph of G is denoted by ΓG . Note that the degree
of a vertex x ∈ V (ΓG ) in the non-cyclic graph ΓG is equal to |G \ CycG (x)|. A.
Abdollahi and A. Mohammadi Hassanabadi in [1] show that ΓG is connected
and diam(ΓG ) ≤ 3. In addition, they show that diam(ΓG ) = 1 if and only
if G is an elementary Abelian 2-group. Also, in [2] they characterize groups
whose non-cyclic graphs have clique numbers at most 4. See [1] and [2] for
more details.
Xuang L. Ma and others in [8], consider The cyclic graph of a finite group G.
They consider some properties of cyclic graph and characterize certain finite
groups whose cyclic graphs have some properties.
In this paper we show that ΓG is isomorphic to K3 ∪(n−4)K1 or K4 ∪(n−5)K1
if and only if G is isomorphic to D8 or D10 , respectively. Also, we characterize
all groups of order n like G in which γ(ΓG ) + γ(ΓG ) ∈ {n, n − 1, n − 2, n − 3},
where |Cyc(G)| = 1. In addition, we prove that γ(ΓG ) = n−1
2 if and only if
ΓG is the union of n−1
copies
of
P
.
2
2
2. On non-cyclic graph
First we consider some algebraic properties of non-cyclic graph and give
some facts that are needed in the next sections. In this paper, we denoted
by An and D2n , alternating group of order n and dihedral group of order 2n,
respectively.
Theorem 1. [1] Let G be a non-locally cyclic group. Then ΓG is connected
and diam(ΓG ) ≤ 3.
Theorem 2. [1] Let G be a non-locally cyclic group. Then diam(ΓG ) = 1 if
and only if G is an elementary Abelian 2-group.

ON NON-CYCLIC GRAPH OF A GROUP

3

Lemma 1. Let G be a non-locally cyclic group and |Cyc(G)| > 1. If [G :
Cyc(G)] = t, then t ≥ 3. Furthermore if |Cyc(G)| ≥ 3, then δ(ΓG ) ≥ 2.
Proof. Let t = 2. Then there is g ∈ G \ Cyc(G) such that G = Cyc(G) ∪
gCyc(G). So V (ΓG ) = gCyc(G). Also for each g1 , g2 ∈ Cyc(G), hgg1 , gg2 i ≤
hg, g1 , g2 i which is a cyclic subgroup of G. Hence ΓG is empty which contradicts
the fact that ΓG is a connected graph. Therefore t ≥ 3. If ℓ = |Cyc(G)| ≥ 3,
then for each x ∈
/ Cyc(G), induced subgraph on xCyc(G) is isomorphic to Kℓ

in ΓG .
Lemma 2. Let G be a non-locally cyclic group of order n and |V (ΓG )| = k.
Then k < n < 2k.
Proof. Let |V (ΓG )| = k. Then n − |Cyc(G)| = k. By Lemma 1, |Cyc(G)| < n2 .
Hence k < n < 2k.

Observation 1. Let G be a non-locally cyclic group and x ∈ V (ΓG ). Then
x−1 ∈ V (ΓG ) and NΓG (x) = NΓG (x−1 ).
Lemma 3. Let G be a non-locally cyclic group. Then δ(ΓG ) ≥ 2.
Proof. Let x, y ∈ V (ΓG ), x be adjacent to y in ΓG and degΓG (x) = 1. We show
that O(y) = 2. On the contrary, let O(y) 6= 2. Then y −1 ∈ V (ΓG ). Since
hx, yi is not cyclic, hx, y −1 i is not cyclic, too. So x and y −1 are adjacent in
ΓG , which contradicts the fact that degΓG (x) = 1. Hence O(y) = 2.
Since Cyc(x) ⊆ CG (x) and |Cyc(x)| > |G|/2, CG (x) = G and so x ∈ Z(G).
Also, since hx, yi is not a cyclic group, O(x) is even and so |G| is even.
Assume that g ∈
/ Cyc(G) ∪ hxi ∪ {y} in that O(x) = t and O(g) = ℓ. Since
hx, gi ∼
= Zt ⊕ Zℓ and hx, gi is cyclic, gcd(t, ℓ) = 1 and so ℓ is odd. Thus
G \ Cyc(G) has exactly two elements of order two which are y and xt/2 . It
is clear that O(xt/2 y) = 2. Hence xt/2 y = xt/2 or xt/2 y = y and so y = e or
xt/2 = e, respectively, which is a contradiction. Therefore δ(ΓG ) ≥ 2.

Lemma 4. Let G be a non-locally cyclic group and x, y ∈ V (ΓG ) such that
O(x) = O(y) = 2. Then x and y are adjacent in ΓG .
Proof. If x and y are not adjacent in ΓG , then hx, yi is a cyclic subgroup of
order four of G, which is wrong.

Lemma 5. Let G be a non-locally cyclic group and x ∈ V (ΓG ). If x is a
universal vertex in ΓG , then O(x) = 2.
Proof. On the contrary let O(x) 6= 2. Then x−1 ∈ V (ΓG ). Since hx, x−1 i = hxi
is a cyclic subgroup of G, x is not adjacent to x−1 in ΓG which contradicts
the fact that x is a universal vertex in ΓG .

Lemma 6. Let G be a non-locally cyclic group. Then in ΓG , the vertices of
degree 1 occur only at the edges.

4

E. VATANDOOST AND Y. GOLKHANDYPOUR

Proof. Let x ∈ V (ΓG ), degΓG (x) = 1 and x is adjacent to y in ΓG . We claim
that O(x) ∈ {3, 4}. For proof, let O(x) = 2. Then by Lemma 4, O(y) 6= 2.
Since hx, yi is cyclic, hx, y −1 i is cyclic subgroup of G, too. Hence y −1 is
adjacent to x in ΓG , which contradicts the fact that degΓG (x) = 1. Hence
O(x) 6= 2.
Obviously, x−1 ∈
/ Cyc(G). If O(x) ≥ 5 and x2 , x3 ∈ Cyc(G), then x ∈ Cyc(G),
which is false. Thus x2 or x3 are not in Cyc(G) and so degΓG (x) ≥ 2, which
is a contradiction. Hence O(x) = 3 or 4. If O(x) = 4, then x2 ∈ Cyc(G) and
so |Cyc(G)| > 1. In any way, y = x−1 . By observation 1, degΓG (y) = 1. This
completed the proof.

Lemma 7. Let G be a non-locally cyclic Abelian group. Then ΓG does not
have both an isolated vertex and a vertex of degree 1.
Proof. Let x and y be an isolated vertex and a vertex of degree one in ΓG ,
respectively. By Lemmas 5 and 6, O(x) = 2 and O(y) = 3 or 4. If O(y) = 3,
then since G is an Abelian group, hx, yi ∼
= Z6 . Hence x is adjacent to y in ΓG ,
which contradicts the fact that x is an isolated vertex in ΓG . If O(y) = 4, then
by Lemma 6, y 2 ∈ Cyc(G). Thus hy 2 , xi is cyclic. This is contradiction.

Theorem 3. Let G be a non-locally cyclic group of order n and |Cyc(G)| = 1.
Then ΓG ∼
= K3 ∪ (n − 4)K1 if and only if n = 8 and G ∼
= D8 .
Proof. If n = 8 and G ∼
= K3 ∪ 4K1 . For proof of converse, let
= D8 , then ΓG ∼
∼
ΓG = K3 ∪ (n − 4)K1 . Also let x1 , x2 , . . . , xn−4 be isolated vertices in ΓG and
a, b, c ∈ V (ΓG ) such that induced subgraph on a, b and c be K3 . By Lemma
5, O(xi ) = 2. It is easy to see that for each g ∈ G, O(g) ≤ 4 and ab = ba,
ac = ca and bc = cb. We have the following two cases.
Case i. Let 3 | n and O(a) = 3. Without loss of generality, suppose b = a−1
and O(c) = 2. So O(ac) = 6 which contradicts the fact that for each g ∈ G,
O(g) ≤ 4.
Case ii. Let 3 ∤ n. By Theorem 2, there exist v ∈ {a, b, c} such that O(v) = 4.
Without loss of generality, suppose O(a) = 4, b = a−1 and c = a2 . Since
O(xi axi ) = O(a), xi axi = a or xi axi = a−1 . If xi axi = a, then xi a = axi and
(xi a)2 = e. So e = x2i a2 = a2 , which is a contradiction. Thus xi axi = a−1 and
so ha, xi i ∼
= D8 .
We claim that G ∼
= ha, x1 i = {e, a, a2 , a3 , x1 , x1 a, x1 a2 , x1 a3 }. For proof of
our claim, let x2 ∈ G \ ha, x1 i. Since x2 a ∈
/ {e, a, a2 , a3 }, O(x2 a) = 2. Thus
−1
x2 ax2 = a . On the other hand, x1 ax1 = a−1 . So x1 ax1 = x2 ax2 . Consequently, (x1 x2 )a = a(x1 x2 ) and so x1 x2 ∈ CG (a). Since CG (a) = hai,
x2 ∈ {x1 , x1 a, x1 a2 , x1 a3 }. Hence x2 ∈ ha, x1 i, which is false. Therefore
G∼

= ha, x1 i, as claimed.

ON NON-CYCLIC GRAPH OF A GROUP

5

Theorem 4. Let G be a non-locally cyclic group of order n and |Cyc(G)| = 1.
Then ΓG ∼
= K4 ∪ (n − 5)K1 if and only if n = 10 and G ∼
= D10 .
Proof. If n = 10 and G ∼
= K4 ∪ 5K1 . For proof of converse,
= D10 , then ΓG ∼
∼
let ΓG = K4 ∪ (n − 5)K1 and x1 , x2 , . . . , xn−5 be isolated vertices in ΓG and
a, b, c, d ∈ V (ΓG ) such that induced subgraph on a, b, c and d be K4 . By
Lemma 5, O(xi ) = 2. It is easy to see that for each g ∈ G, O(g) ≤ 5.
By Theorem 2, there exist t ∈ {a, b, c, d} such that O(t) 6= 2. Furthermore, by
Lemma 4, for every x ∈ {a, b, c, d}, O(x) 6= 4. We consider the following cases.
Case i. Let u, v ∈ {a, b, c, d} such that O(u) = 2 and O(v) = 3. Then since
uv = vu, O(uv) = 6 which contradicts the fact that for each g ∈ G, O(g) ≤ 5.
Case ii. Let for each u ∈ {a, b, c, d}, O(u) = 3. Without loss of generality, let
c = a−1 and d = b−1 . Then ha, bi ∼
= Z3 ⊕ Z3 . Since a is adjacent to b in ΓG ,
ha, bi is a cyclic subgroup of G, which is false.
Case iii. If O(a) = 5, then b = a2 , c = a3 and d = a4 . Since O(xi axi ) = O(a),
xi axi ∈ {a, a2 , a3 , a4 }. If xi axi ∈ {a, a2 , a3 }, then (axi )2 ∈ {a2 , a3 , a4 }. On
the other hand, O(axi ) = 2 and so e ∈ {a2 , a3 , a4 } which is false. Hence
axi = xi a4 and so ha, xi i ∼
= D10 .
By the similar argument as in proof of Theorem 3, it can be proven that
G∼

= ha, x1 i. Therefore G is isomorphic to D10 .
Theorem 5. Let G be a non-locally cyclic group. Then ΓG ∼
= Cn if and only
if n = 3 and G ∼
= Z2 ⊕ Z2 .
Proof. If G ∼
= Z2 ⊕ Z2 , then ΓG is isomorphic to C3 . In the following we
consider the proof of converse.
It is clear that for every x ∈ G \ {e}, |CG (x)| ≥ |G| − 2. Then CG (x) = G and
so G is an abelian group. On the other hand, by Theorem 1, n ≤ 7. If n = 4
and ΓG is isomorphic to C4 , then by Lemma 2, 4 ≤ |G| < 8. Since G is an
abelian group, G is cyclic, which is not true.
Suppose that 5 ≤ n ≤ 7. By Lemma 4, suppose that x ∈ V (ΓG ) such that
O(x) 6= 2. Then x−1 ∈
/ NΓG (x). By Observation 1, NΓG (x) = NΓG (x−1 ),
which is a contradiction.

Lemma 8. Let G be a non-locally cyclic group and x, y ∈ V (ΓG ) such that
x and y are adjacent in ΓG . Then |NΓG (x) ∩ NΓG (y)| ≥ 1. Furthermore, ΓG
does not have Ci as a component, where i ≥ 4.
Proof. By Lemma 4, at least O(x) 6= 2 or O(y) 6= 2. Without loss of generality,
let O(x) 6= 2. Since hx, yi is cyclic group, hx−1 , yi is cyclic, too. Hence
x−1 ∈ NΓG (x) ∩ NΓG (y) and so |NΓG (x) ∩ NΓG (y)| ≥ 1. Now it is clear that
ΓG does not have Ci as a component.


6

E. VATANDOOST AND Y. GOLKHANDYPOUR

3. On acceptable groups
In this section, we consider Algebraic structures of non-cyclic graph on
acceptable groups and show if G is an acceptable group, then ΓG is constructed
by both copies of P2 and isolated vertices.
Definition 1. Let G be a group. Write S and T for the set of elements of G
of order two and three, respectively. Then G is acceptable when neither S nor
T is empty and G = S ∗ ∪ T , where S ∗ = S ∪ {e}.
Lemma 9. [3] If G is acceptable, then either S ∗ ≤ G or T ∗ ≤ G (” ≤ ”
means ”is a subgroup of”).
Theorem 6. Let G be a non-locally cyclic group. If G is an acceptable group,
then ΓG is isomorphic to some copies of P2 together with isolated vertices.
Proof. Let G be an acceptable group. Write S(or T ) for the set of elements
of G of order two(or three). Also let x, y ∈ S and z, t ∈ T , where z 6= t−1 . If
hx, zi is a cyclic subgroup of G, then O(xz) = 6 which contradicts the fact that
G is an acceptable group. Also it is clear that hx, yi and hz, ti are not cyclic.
Hence for each u ∈ S and v ∈ T , CycG (u) = {e, u} and CycG (v) = {e, v, v −1 }.
Therefore |Cyc(G)| = 1 and ΓG is isomorphic to some copies of P2 together
with isolated vertices.

4. On domination number of non-cyclic graph
In this section, domination number on some non-cyclic graphs is considered.
Theorem 7. [10] Let Γ be a graph with no isolated vertex. Then γ(Γ) ≤ n2 .
Theorem 8. [4] Let Γ be a graph without isolated vertices on n vertices such
that n is even. Then γ(Γ) = n2 if and only if the components of Γ are C4 or
H ◦ K1 where H is a connected graph.
Theorem 9. [7] Let Γ be a graph on n vertices. Then
i) γ(Γ) + γ(Γ) ≤ n + 1.
ii) γ(Γ)γ(Γ) ≤ n.
Lemma 10. [6] Let Γ be a graph on n vertices. Then γ(Γ) = 1 if and only
if ∆(Γ) = n − 1.
Theorem 10. Let G be a non-locally cyclic group of order n, where n and
|Cyc(G)| = t are odd. Then γ(ΓG ) = n−t
2 if and only if t = 1 and ΓG is
n−1
isomorphic to 2 copies of P2 .

ON NON-CYCLIC GRAPH OF A GROUP

7

Proof. Let γ(ΓG ) = n−t
2 . If t > 1, then since t is odd, t > 2. By Lemma
1, δ(ΓG ) ≥ 2. Also by Theorem 8, the components of ΓG are C4 or H ◦ K1
where H is a connected graph. Hence the components of ΓG are C4 which
contradicts Lemma 8. So t = 1.
Now let γ(ΓG ) = n−1
2 . Since n is odd, by Lemma 5, ΓG does not have isolated
vertex. By Theorem 8, the components of ΓG are isomorphic to C4 or H ◦ K1 .
By Lemma 8, ΓG does not have C4 as a component and so the components of
ΓG are isomorphic to H ◦ K1 . By Lemma 6, ΓG is isomorphic to n−1
2 copies
of P2 . The proof of converse is easy.

Theorem 11. Let G be a non-locally cyclic group of order n, |Cyc(G)| = 1.
Then γ(ΓG ) < n−1
2 .
n−1
Proof. Since ΓG is a connected graph, γ(ΓG ) ≤ n−1
2 . If γ(ΓG ) = 2 , then n
is odd. By Theorem 8, the components of ΓG are isomorphic to C4 or H ◦ K1
where H is a connected graph. By Lemma 3, components of ΓG are of type
C4 . Since ΓG is a connected graph, ΓG ∼
= C4 . By Theorem 5, ΓG does not have
C4 as a component, which is a contradiction. Therefore γ(ΓG ) < n−1

2 .

Theorem 12. Let G be a non-locally cyclic group of order n and |Cyc(G)| = 1.
Then
i) γ(ΓG ) + γ(ΓG ) = n if and only if G is an elementary Abelian 2-group.
ii) γ(ΓG ) + γ(ΓG ) = n − 1 if and only if G ∼
= S3 .
iii) γ(ΓG ) + γ(ΓG ) = n − 2 if and only if G ∼
= D8 .
iv) γ(ΓG ) + γ(ΓG ) = n − 3 if and only if either G ∼
= D10 or G ∼
= Z3 ⊕ Z3 .
Proof. i) Let γ(ΓG ) + γ(ΓG ) = n. By Theorem 11, γ(ΓG ) < n−1
2 . So γ(ΓG ) >
n−1
2 and so ΓG has at least one isolated vertex. Thus γ(ΓG ) = 1 and γ(ΓG ) =
n − 1. Hence ΓG is isomorphic to a complete graph. By Theorem 2, G is
an elementary Abelian 2-group. Conversely, let G be an elementary Abelian
2-group. By Theorem 2, ΓG is a complete graph. So γ(ΓG ) = 1 and γ(ΓG ) =
n − 1. Thus γ(ΓG ) + γ(ΓG ) = n.
n−1
ii) Let γ(ΓG )+γ(ΓG ) = n−1. By Theorem 11, γ(ΓG ) < n−1
2 . So γ(ΓG ) > 2 .
Hence ΓG has at least one isolated vertex. Thus γ(ΓG ) = 1 and so γ(ΓG ) =
n − 2. Hence ΓG is a union of one copy of P2 and isolated vertices denoted
by {x1 , x2 , . . . , xn−3 }. By Lemma 6, G has exactly two elements of order 3
that are denoted by a and b such that a = b−1 . Obviously, O(xi axi ) = O(a)
and so xi axi = a or a−1 . If xi axi = a, then xi a = axi and (xi a)2 = e. On
the other hand, (xi a)2 = x2i a2 = a2 . So a2 = e, which is a contradiction.
Hence xi axi = a−1 and so ha, xi i ∼
= S3 . By the similar argument as in proof
of Theorem 3, it can be proven that G = ha, x1 i ∼
= S3 . Conversely, γ(ΓS3 ) = 1
and γ(ΓS3 ) = 4. So the result is achieved.
iii) Let γ(ΓG ) + γ(ΓG ) = n − 2. By Theorem 11, γ(ΓG ) < n−1
2 . The following

8

E. VATANDOOST AND Y. GOLKHANDYPOUR

two cases will be considered.
n−1
n−1
Case i. If γ(ΓG ) = n−3
2 , then γ(ΓG ) = 2 . By Theorem 10, ΓG is 2 copies
of P2 and so ΓG is a complete multipartite graph. Hence γ(ΓG ) = 2. It follows
that n = 7, which is impossible.
n−1
and so ΓG has at least one
Case ii. If γ(ΓG ) < n−3
2 , then γ(ΓG ) >
2
isolated vertex. Thus γ(ΓG ) = 1 and γ(ΓG ) = n − 3. Let V (ΓG ) = A ∪ B
in that A = {a, b, c, d} and B = {x1 . . . xn−5 }. We have induced subgraph on
B is isomorphic to K n−5 . By Lemmas 6 and 8 and γ(ΓG ) = n − 3, induced
subgraph on A is isomorphic with two copies of P2 or a union of K3 and an
isolated vertex.
Suppose that induced subgraph on A is isomorphic with two copies of P2 . By
Lemma 5, B is a set of elements of order two. Also, by proof of Lemma 6, A
is a set of elements of order 3.
Hence G is an acceptable group and so by Lemma 9, A ∪ {e} ≤ G or
B ∪ {e} ≤ G. If A ∪ {e} ≤ G, then since |A ∪ {e}| = 5, it follows that 3 | 5
which is not true. Thus B ∪ {e} ≤ G. Since |B ∪ {e}| ≤ |G|/2, we have
n ≤ 8. But there is no group of order less than or equal to 8 such that has
four elements of order 3, which is a contradiction.
Hence ΓG is isomorphic to a union of isolated vertices denoted by x1 , . . . , xn−4
and three vertices {a, b, c} such that induced subgraph on {a, b, c} is isomorphic
to K3 . By Theorem 3, G ∼
= D8 . Conversely, γ(ΓD8 ) = 1 and γ(ΓD8 ) = 5.
iv) Let γ(ΓG ) + γ(ΓG ) = n − 3. By Theorem 11, γ(ΓG ) < n−1
2 . The following
three cases will be considered.
n−3
Case i. If γ(ΓG ) = n−3
2 , then γ(ΓG ) = 2 . By Theorem 9, γ(ΓG )γ(ΓG ) ≤
2
2
n − 1. Hence ( n−3
2 ) ≤ n − 1 and so n − 10n + 13 ≤ 0 implies that 2 ≤ n ≤ 8.
Since γ(ΓG ) = n−3
2 , n ∈ {5, 7}, which contradicts the fact that G is not a
cyclic group.
n−1
n−1
Case ii. If γ(ΓG ) = n−5
2 , then γ(ΓG ) = 2 . By Theorem 10, ΓG is 2
copies of P2 and so ΓG is complete multipartite graph. Hence γ(ΓG ) = 2. It
follows that n = 9 and so G ∼
= Z3 ⊕ Z3 .
.
Then γ(ΓG ) > n−1
Case iii. Let γ(ΓG ) < n−5
2
2 and so ΓG has at least one
isolated vertex. Thus γ(ΓG ) = 1 and γ(ΓG ) = n − 4.
Assume that u ∈ V (ΓG ). If deg(u) > 3, then γ(ΓG ) < n − 4, which is a
contradiction. Hence for each u ∈ V (ΓG ), degΓG (u) ≤ 3 and so O(u) ≤ 5. We
consider the following subcases.
A. For each u ∈ V (ΓG ), degΓG (u) ≤ 1.
In this case, ΓG is isomorphic to a union of three copies of P2 and n−7 isolated
vertices. By Lemmas 5 and 6, G is a group which is constructed from set of
elements of order three and set of elements of order two that are defined by
T and S, respectively. Hence G is an acceptable group and so by Lemma 9,
T ∪ {e} ≤ G or S ∪ {e} ≤ G. Since 3 ∤ |T ∪ {e}| = 7, T ∪ {e}  G. Hence

ON NON-CYCLIC GRAPH OF A GROUP

9

S ∪ {e} ≤ G. Since |S ∪ {e}| ≤ |G|/2, we have n ≤ 12.
Since there is no group with n ≤ 11 which have exactly six elements of order 3,
n = 12. Then G ∼
= A4 , D12 or L = ha, b ; a6 = 1, a3 = b2 , b−1 ab = a−1 . Since
G has exactly six elements of order 3, G ∈
/ {A4 , D12 }. On the other hand, in
L, O(b) = 4, which contradicts the fact that G is an acceptable group.
B. For each u ∈ V (ΓG ), deg(u) ≤ 2.
Assume that u, v ∈ V (ΓG ) such that degΓG (u) = degΓG (v) = 2. If u and v are
not adjacent in ΓG , then γ(ΓG ) < n − 4, which is wrong. Also, if u and v are
adjacent in ΓG , then by Lemmas 6 and 8, u, v ∈ V (K3 ). So ΓG is isomorphic
to a union of some copies of K3 , P2 and isolated vertices. If ΓG have more than
one copy of K3 as a component, then γ(ΓG ) ≤ n − 5, which is a contradiction.
Since γ(ΓG ) = n−4, ΓG is isomorphic to a union of one copy of C3 , one copy of
P2 and isolated vertices. Suppose that V (K3 ) = {u1 , u2 , u3 }, V (P2 ) = {v1 , v2 }
and xi is isolated vertex, for 1 ≤ i ≤ n − 6. By Lemma 4, we can assume that
O(u1 ) 6= 2. If O(u1 ) = 3 and u2 = u−1
1 , then O(u3 ) = 2. Since hu1 , u3 i is
cyclic, there exist an element of order six in G which is a contradiction. Hence
O(u1 ) = 4 and so u2 = u21 and u3 = u31 . On the other hand, by Lemma 3,
O(v1 ) = O(v2 ) = 3 and by Lemma 5, O(xi ) = 2. Therefore n = 2ℓ × 3.
By Sylow theorem, there exist H, K ≤ G such that |H| = 2ℓ and |K| = 3.
Also K = {e, v1 , v1−1 } and Z(H) 6= 1. Obviously, for each h ∈ G \ {u1 , u3 },
O(hv1 h) = O(v1 ) = 3. Thus hv1 h = v1 or v1−1 . If hv1 h = v1 , then v1 h = hv1
and so O(v1 h) = 6, which is a contradiction. So
hv1 h = v1−1 or v1 h = hv1−1 or hv1 = v1−1 h.

(4.1)

Assume that z ∈ Z(H) and O(z) = 2. Also let h ∈ G \ {u1 , u3 , z}. By
equalities 4.1, we have
(zh)v1 = (hz)v1 = h(zv1 ) = h(v1−1 z) = (hv1−1 )z = (v1 h)z = v1 (zh).
Hence zh ∈ C(v1 ). On the other hand, O(zh) = 2 and C(v1 ) = {e, v1 , v1−1 }.
So zh ∈ {v1 , v1−1 }, which is a contradiction.
C. There exist u ∈ V (ΓG ) such that degΓG (u) = 3 and NΓG (u) = {x, y, z}.
C.1. If O(u) = 2, then by Lemma 4, for each v ∈ N (u), O(v) = 3 or 4. If
O(v) = 3, then hu, vi has an element of order six which is false. Thus O(x) = 4.
If x−1 ∈
/ N (u), then hx−1 , ui is cyclic and so u and x−1 are adjacent in ΓG
which is wrong. Hence x−1 ∈ N (u). Without loss of generality, let y = x−1 .
Then z −1 = z and so O(z) = 2, which contradicts Lemma 4.
C.2. Assume that O(u) = 3 and without loss of generality, let x = u−1 . By
Observation 1, NΓG (x) = NΓG (u). We claim that z = y −1 . For proof let
z 6= y −1 . Since hu, y −1 i is cyclic, u is adjacent to y −1 in ΓG , which is false.
Hence z = y −1 , as claimed and so y is adjacent to z in ΓG . Therefore induced
subgraph on N [u] is isomorphic to K4 . So ΓG ∼
= K4 ∪ (n − 5)K1 . By Theorem

10

E. VATANDOOST AND Y. GOLKHANDYPOUR

4, G ∼
= D10 .
C.3. Assume that O(u) = 4 and without loss of generality, let x = u2 and
y = u3 . We have
hu2 , zi ≤ hu, zi.
Since hu, zi is cyclic, hu2 , zi is cyclic, too. If O(z) = 2, then hu2 , zi is Klein four
group, which is wrong. Also if O(z) = 3, then hu2 , zi has an element of order
six, which is a contradiction. Suppose that O(z) = 4 or 5. By Observation 1,
NΓG (z) = NΓG (z −1 ). Since u ∈ NΓG (z), u ∈ NΓG (z −1 ). So z −1 ∈ {u2 , u3 , z}.
Since O(z) = 4, z −1 ∈
/ {u2 , z}. Hence z −1 = u3 and so z = u, which is a
contradiction.
C.4. Suppose that O(u) = 5. Then induced subgraph on NΓG [u] is isomorphic
to K4 . Hence ΓG ∼
= K4 ∪ (n − 5)K1 . By Theorem 4, G ∼
= D10 .
The proof of converse is straightforward.

Acknowledgement
We thank Professor Saeed Akbari1 for his comments and expert of our
paper.
References
[1] A. Abdollahi, A. Mohammadi Hassanabadi, Non-cyclic graph of a group, Communication in Algebra, 35:(2057-2081), 2007.
[2] A. Abdollahi, A. Mohammadi Hassanabadi, Non-cyclic graph associated with a group,
J. Algebra Appl., 8:(243-259), 2009.
[3] E. D. Bolker, Bryn Mawr College, Groups whose elements are ordered two or three, The
American Mathematical Monthly, Vol. 79, No. 9, (1007-1010), 1972.
[4] J. F. Fink, M. S. Jacobson, L. F. Kinch and J. Roberts, On graphs having domination
number half their order, Period. Math. Hunger., 16(287-293), 1985.
[5] P. Flach, L. Volkmann, Estimations for the domination number of a graph, Discrete
Math, (145-151), 1990.
[6] W. Haynes, T. Hedetniemi, J. Slater, Fundementals of domination in graphs, MARCEL
DEKKER INC., 1998.
[7] F. Jaeger, C. Payan, Relation du type Nordhaus-Gaddum pour le numbered absorption
dun graphe simple, C. R. Acard. Sci. Paris, 274(728-730), 1972.
[8] Xuang L. Ma, Hua Q. Wei, G. Zhong, The cyclic graph of a finite group, Hiudawi Pub.
Co. Algebra, Vol. 2013, Article ID. 1072265, 7 pages.
[9] B. H. Neumann, Groups whose elements have bounded orders, J. London Math. Soc.,
12, 195, 1937.
[10] O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. PubL, 38 (Amer. Math. Soc,
Providence, RI), 1962.
[11] C. Payan, Sur le nombre d’absorption d’un graphe simple, Cahiers Centre Etudes Rech.
Oper. B.3.4, 171, 1975.
1Department of Mathematical Sciences, Sharif University of Technology, P.O.Box: 113659415, Tehran, Iran. Email: s− akbari@sharif.edu

ON NON-CYCLIC GRAPH OF A GROUP

11

[12] H. B. Walikar, B. D. Acharya, and E. Sampathkumar, Recent develop- developments in
the theory of domination in graphs, In MRI Lecture Notes in Math., Mahta Research
Instil, Allahabad, volume 1, 1979.
IKI University, Faculty of Sciences, Department of Mathematics, Qazvin,
Iran
E-mail address: vatandoost@sci.ikiu.ac.ir
IKI University, Faculty of Sciences, Department of Mathematics, Qazvin,
Iran
E-mail address: y.golkhandypour@edu.ikiu.ac.ir

