Some properties of various graphs associated with finite groups
In this paper we investigate some properties of the power graph and commuting graph associated with a finite group, using their tree-numbers. Among other things, it is shown that the simple group L₂(7) can be characterized through the tree-number of its power graph. Moreover, the classification of g...
Gespeichert in:
| Datum: | 2021 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2021
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/188706 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Some properties of various graphs associated with finite groups / X.Y. Chen, A.R. Moghaddamfar, M. Zohourattar // Algebra and Discrete Mathematics. — 2021. — Vol. 31, № 2. — С. 195–211. — Бібліогр.: 64 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-188706 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1887062023-03-12T01:29:06Z Some properties of various graphs associated with finite groups Chen, X.Y. Moghaddamfar, A.R. Zohourattar, M. In this paper we investigate some properties of the power graph and commuting graph associated with a finite group, using their tree-numbers. Among other things, it is shown that the simple group L₂(7) can be characterized through the tree-number of its power graph. Moreover, the classification of groups with power-free decomposition is presented. Finally, we obtain an explicit formula concerning the tree-number of commuting graphs associated with the Suzuki simple groups. 2021 Article Some properties of various graphs associated with finite groups / X.Y. Chen, A.R. Moghaddamfar, M. Zohourattar // Algebra and Discrete Mathematics. — 2021. — Vol. 31, № 2. — С. 195–211. — Бібліогр.: 64 назв. — англ. 1726-3255 DOI:10.12958/adm1197 2020 MSC: 05C25, 20D05, 20D06. http://dspace.nbuv.gov.ua/handle/123456789/188706 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
In this paper we investigate some properties of the power graph and commuting graph associated with a finite group, using their tree-numbers. Among other things, it is shown that the simple group L₂(7) can be characterized through the tree-number of its power graph. Moreover, the classification of groups with power-free decomposition is presented. Finally, we obtain an explicit formula concerning the tree-number of commuting graphs associated with the Suzuki simple groups. |
| format |
Article |
| author |
Chen, X.Y. Moghaddamfar, A.R. Zohourattar, M. |
| spellingShingle |
Chen, X.Y. Moghaddamfar, A.R. Zohourattar, M. Some properties of various graphs associated with finite groups Algebra and Discrete Mathematics |
| author_facet |
Chen, X.Y. Moghaddamfar, A.R. Zohourattar, M. |
| author_sort |
Chen, X.Y. |
| title |
Some properties of various graphs associated with finite groups |
| title_short |
Some properties of various graphs associated with finite groups |
| title_full |
Some properties of various graphs associated with finite groups |
| title_fullStr |
Some properties of various graphs associated with finite groups |
| title_full_unstemmed |
Some properties of various graphs associated with finite groups |
| title_sort |
some properties of various graphs associated with finite groups |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2021 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/188706 |
| citation_txt |
Some properties of various graphs associated with finite groups / X.Y. Chen, A.R. Moghaddamfar, M. Zohourattar // Algebra and Discrete Mathematics. — 2021. — Vol. 31, № 2. — С. 195–211. — Бібліогр.: 64 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT chenxy somepropertiesofvariousgraphsassociatedwithfinitegroups AT moghaddamfarar somepropertiesofvariousgraphsassociatedwithfinitegroups AT zohourattarm somepropertiesofvariousgraphsassociatedwithfinitegroups |
| first_indexed |
2025-07-16T10:53:29Z |
| last_indexed |
2025-07-16T10:53:29Z |
| _version_ |
1837800578992832512 |
| fulltext |
“adm-n2” — 2021/7/19 — 10:26 — page 195 — #31
© Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 31 (2021). Number 2, pp. 195–211
DOI:10.12958/adm1197
Some properties of various graphs associated
with finite groups∗
X. Y. Chen, A. R. Moghaddamfar, and M. Zohourattar
Communicated by A. Yu. Olshanskii
Abstract. In this paper we investigate some properties
of the power graph and commuting graph associated with a finite
group, using their tree-numbers. Among other things, it is shown
that the simple group L2(7) can be characterized through the tree-
number of its power graph. Moreover, the classification of groups
with power-free decomposition is presented. Finally, we obtain an
explicit formula concerning the tree-number of commuting graphs
associated with the Suzuki simple groups.
1. Notation and definitions
We will consider finite simple graphs Γ = (VΓ, EΓ), where VΓ 6= ∅
and EΓ are the vertex set and edge set of Γ, respectively. A clique (or
a complete set) in Γ is a subset of VΓ consisting of pairwise adjacent
vertices (we do not require that it be a maximal complete set). Especially,
a complete graph is a graph in which the vertex set is a complete set.
A coclique (edgeless graph or independent set) in Γ is a set of pairwise
∗This work was done during the first and second authors had a visiting position at
the Department of Mathematical Sciences, Kent State University, USA. They would
like to thank the hospitality of the Department of Mathematical Sciences of KSU. The
first author thanks Cultivation Programme for Young Backbone Teachers in Henan
University of Technology, the Project of Henan Province (182102410049), and NSFC
(11926330, 11926326, 11971189, 11771356).
2020 MSC: 05C25, 20D05, 20D06.
Key words and phrases: Power graph, commuting graph, tree-number, simple
group.
“adm-n2” — 2021/7/19 — 10:26 — page 196 — #32
196 Properties of graphs associated with groups
nonadjacent vertices. The independence number, denoted by α(Γ), is the
size of the largest coclique in Γ.
A spanning tree for a graph Γ is a subgraph of Γ which is a tree
and contains all the vertices of Γ. The tree-number (or complexity) of
a graph Γ, denoted by κ(Γ), is the number of spanning trees of Γ (0
if Γ is disconnected), see [57]. The famous Cayley formula shows that
the complexity of the complete graph with n vertices is given by nn−2
(Cayley’s formula).
In this paper, we shall be concerned with some graphs arising from
finite groups. Indeed, there are various ways to associate a certain graph
to a finite group (for example see [3], [56], [60]). Two well known graphs
associated with groups are commuting graphs and power graphs, as defined
more precisely below. Let G be a finite group and X a nonempty subset
of G:
• The (undirected) power graph P(G,X), has X as its vertex set with
two distinct elements of X joined by an edge when one is a power
of the other. The directed power graph ~P(G,X) is a directed graph
with the set X of vertices and with all edges (x, y) such that x 6= y
and y is a power of x.
• The commuting graph C(G,X), has X as its vertex set with two
distinct elements of X joined by an edge when they commute in G.
Clearly, power graph P(G,X) is a subgraph of C(G,X). In the case
X = G, we will simply write C(G) and P(G) instead of C(G,G) and
P(G,G), respectively.
The directed power graph of a group was introduced by Kelarev and
Quinn [36]. The definition was formulated so that it applied to semigroups
as well. Accordingly, the power graphs of semigroups were first considered
in [39], [37] and [38]. It is also explained in the survey [1] that the definition
given in [36] covers all undirected graphs as well. This means that the
undirected power graphs were also defined in [36] (see [1] for more detailed
explanations). All of these papers used only the brief term power graph,
even though they covered both directed and undirected power graphs. The
investigation of graphs like these is very important, because they have
valuable applications presented, for example, in the books [34], [35] and
the survey [40].
The power and commuting graphs have been also considered in many
other papers, see for instance [2], [4]-[7], [10]-[18], [20,22,23], [25]-[28], [31]-
[33], [41]-[44], [46]-[48], [50]-[55], [58, 59, 63]. In particular, in [45, Lemma
4.1], it is shown that P(G) = C(G) if and only if G is a cyclic group of
“adm-n2” — 2021/7/19 — 10:26 — page 197 — #33
X. Chen, A. Moghaddamfar, M. Zohourattar 197
prime power order, or a generalized quaternion 2-group, or a Frobenius
group with kernel a cyclic p-group and complement a cyclic q-group,
where p and q are distinct primes. Obviously, when 1 ∈ X, the power
graph P(G,X) and the commuting graph C(G,X) are connected, and we
can talk about the complexity of these graphs. For convenience, we put
κP(G,X) = κ(P(G,X)), κP(G) = κ(P(G)), κC(G,X) = κ(C(G,X)) and
κC(G) = κ(C(G)). Also, instead of κP(G,X) and κC(G,X), we simply
write κP(X) and κC(X), if it does not lead to confusion. All groups under
discussion in this paper are finite and our group theoretic notation is
mostly standard and follows that in [19].
2. General lemmas
We first establish some notation which will be used repeatedly in the
sequel. Given a graph Γ, we denote by AΓ and DΓ the adjacency matrix
and the diagonal matrix of vertex degrees of Γ, respectively. The Laplacian
matrix of G is defined as LΓ = DΓ −AΓ. Clearly, LΓ is a real symmetric
matrix and its eigenvalues are nonnegative real numbers. The Laplacian
spectrum of Γ is
Spec(LΓ) = (µ1(Γ), µ2(Γ), . . . , µn(Γ)) ,
where µ1(Γ) > µ2(Γ) > · · · > µn(Γ), are the eigenvalues of LΓ arranged in
weakly decreasing order, and n = |V (Γ)|. Note that, µn(Γ) is 0, because
each row sum of LΓ is 0. Instead of AΓ, LΓ, and µi(Γ) we simply write
A, L, and µi if it does not lead to confusion.
For a graph with n vertices and Laplacian spectrum
µ1 > µ2 > · · · > µn = 0,
it has been proved [8, Corollary 6.5] that:
κ(Γ) =
µ1µ2 · · ·µn−1
n
. (1)
The vertex–disjoint union of the graphs Γ1 and Γ2 is denoted by Γ1⊕Γ2.
Define the join of Γ1 and Γ2 to be Γ1 ∨ Γ2 = (Γc
1 ⊕ Γc
2)
c. Evidently this is
the graph formed from the vertex–disjoint union of the two graphs Γ1,Γ2,
by adding edges joining every vertex of Γ1 to every vertex of Γ2. Now,
one may easily prove the following (see also [49]).
“adm-n2” — 2021/7/19 — 10:26 — page 198 — #34
198 Properties of graphs associated with groups
Lemma 1. Let Γ1 and Γ2 be two graphs on disjoint sets with m and n
vertices, respectively. If
Spec(LΓ1
) = (µ1(Γ1), µ2(Γ1), . . . , µm(Γ1)) ,
and
Spec(LΓ2
) = (µ1(Γ2), µ2(Γ2), . . . , µn(Γ2)) ,
then the following hold:
(1) The eigenvalues of Laplacian matrix LΓ1⊕Γ2
are:
µ1(Γ1), . . . , µm(Γ1), µ1(Γ2), . . . , µn(Γ2).
(2) The eigenvalues of Laplacian matrix LΓ1∨Γ2
are:
m+ n, µ1(Γ1) + n, . . . , µm−1(Γ1) + n,
µ1(Γ2) +m, . . . , µn−1(Γ2) +m, 0.
Two Examples. (1) Consider the complete bipartite graph Ka,b = Kc
a∨Kc
b .
Then, by Lemma 1 (2), the eigenvalues of Laplacian matrix LKc
a∨K
c
b
are:
a+ b, b, b, . . . , b
︸ ︷︷ ︸
(a−1)−times
, a, a, . . . , a
︸ ︷︷ ︸
(b−1)−times
, 0.
Using Eq. (1) we get κ(Ka,b) = ba−1ab−1.
(2) A graph Γ is a split graph if its vertex set can be partitioned into
a clique C and an independent set I, where VΓ = C ⊎ I is called a split
partition of Γ (see [24]). Now, consider the split graph Γ = Ka∨Kc
b . Again,
by Lemma 1 (2), the eigenvalues of Laplacian matrix LKa∨Kc
b
are:
a+ b, a+ b, a+ b, . . . , a+ b
︸ ︷︷ ︸
(a−1)−times
, a, a, . . . , a
︸ ︷︷ ︸
(b−1)−times
, 0,
and it follows from Eq. (1) that κ(Γ) = (a+ b)a−1ab−1.
Next lemma determines the complete commuting graphs and power
graphs.
Lemma 2. Let G be a finite group. Then, we have
(1) The commuting graph C(G) is complete iff G is an abelian group.
(2) The power graph P(G) is complete iff G is a cyclic p-group for some
prime p (see Theorem 2.12 in [14]).
“adm-n2” — 2021/7/19 — 10:26 — page 199 — #35
X. Chen, A. Moghaddamfar, M. Zohourattar 199
An immediate consequence of Lemma 2 is that κP(Zpn) = pn(p
n−2)
and if X ⊂ G is a commuting set, then κC(G,X) = |X||X|−2. We will use
these facts without further references.
Lemma 3. Let M and N be subgroups of a group G such that M ∩N = 1.
Let x ∈ M and y ∈ N be two arbitrary nontrivial elements. Then, x and
y are nonadjacent in P(G) as two vertices. In particular, if m > 1 and
X = ∪m
j=1Gj, where 1 < Gj < G and Gi ∩Gj = 1 for i 6= j, then we have
P(X#) =
m⊕
j=1
P
(
G#
j
)
,
where X# = X \ {1} and G#
j = Gj \ {1}.
Proof. It is easy to see that 〈x〉∩〈y〉 ⊆ M ∩N = 1, which forces 〈x〉 6⊆ 〈y〉
and 〈y〉 6⊆ 〈x〉.
As an immediate consequence of Lemma 3, we obtain
Corollary 1. Let G be a finite group. Then the following hold:
(1) If G has even order, then Inv(G), the set of involutions of G, forms
an independent set of P(G).
(2) Any pair of elements in G with relatively prime orders forms an
independent set of P(G), especially we have α(P(G)) > |π(G)|, where
π(G) denotes the set of all prime divisors of |G|.
A universal vertex is a vertex of a graph that is adjacent to all other
vertices of the graph. The following lemma [12, Proposition 4] determines
the set of universal vertices of the power graph of G, in general case.
Lemma 4. Let G be a finite group and S the set of universal vertices of
the power graph P(G). Suppose that |S| > 1. Then one of the following
occurs:
(a) G is cyclic of prime power order, and S = G;
(b) G is cyclic of non-prime-power order n, and S consists of the identity
and the generators of G, so that |S| = 1 + φ(n);
(c) G is generalized quaternion, and S contains the identity and the
unique involution in G, so that |S| = 2.
Lemma 5. [50, Theorem 3.4] If H1, H2, . . . , Ht are nontrivial subgroups
of a group G such that Hi ∩Hj = {1}, for each 1 6 i < j 6 t, then we
have κP(G) > κP(H1)κP(H2) · · ·κP(Ht).
“adm-n2” — 2021/7/19 — 10:26 — page 200 — #36
200 Properties of graphs associated with groups
Lemma 6. [50, Lemma 6.1] Let G be a finite nonabelian simple group
and let p be a prime dividing the order of G. Then G has at least p2 − 1
elements of order p, or equivalently, there is at least p+1 cyclic subgroups
of order p in G.
3. Main results
3.1. Power graphs
We begin with some elementary but useful results of power graphs.
Before stating the results, we need to introduce some additional notation.
Let X be a nonempty subset of G#, the set of nonidentity elements of G.
We denote by 1X the bipartite graph with partite sets {1} and X. Let
φ denote Euler’s totient function, so that φ(n) = |Z×
n |. We will preserve
these notation throughout this section.
Lemma 7. Let G be a group and H be a proper subgroup of G. If m is
the order of an element of G \H, then we have
κP(G) > (φ(m) + 1)φ(m)−1 κP(H).
In particular, κP(G) > κP(H), with equality if and only if G is a Frobenius
group with kernel H and complement C of order 2.
Proof. Let x be an element in G \H of order m. Set
Ωx = {y | 〈y〉 = 〈x〉} ∪ {1}.
Clearly, Ωx∩H = 1 and |Ωx| = φ(m)+1. Note that the induced subgraph
P(G,Ωx) is a complete graph, that is P(G,Ωx) = Kφ(m)+1. Now, if
TΩx
and TH are two arbitrary spanning trees of P(G,Ωx) and P(G,H),
respectively, then TG = TΩx
∪ TH ∪ 1G\(Ωx∪H) is a spanning tree of P(G).
Thus, by product rule the number of such spanning trees of P(G) is equal
to
κP(Ωx) · κP(H) · 1 = (φ(m) + 1)φ(m)−1κP(H). (by Cayley’s formula)
This shows that the following inequality holds:
κP(G) > (φ(m) + 1)φ(m)−1κP(H),
“adm-n2” — 2021/7/19 — 10:26 — page 201 — #37
X. Chen, A. Moghaddamfar, M. Zohourattar 201
as required. Finally, since for each positive integer m,
(φ(m) + 1)φ(m)−1
> 1,
it follows that κP(G) > κP(H).
The preceding argument suggests how to construct a spanning tree
of P(G) through a spanning tree of P(G,H). In fact, if TH is a spanning
tree of P(G,H), then TG = TH ∪ 1G\H is a spanning tree of P(G), which
leads again to the inequality κP(G) > κP(H). Moreover, the equality
holds if and only if P(G,G \H) is a null graph and there are no edges
between vertices in G \H and H#. We argue under these conditions that
G is a Frobenius group with kernel H and complement C of order 2. We
first observe that every element in G \H is an involution. Also, for all
x ∈ G \ H and h ∈ H, xh ∈ G \ H and so (xh)2 = 1, or equivalently
x−1hx = h−1. This shows that H is a normal subgroup of G and the cyclic
subgroup C = 〈x〉 of order 2 acts on H by conjugation which induces
a fixed-point-free automorphism of H. Hence, G = HC is a Frobenius
group with kernel H and complement C, as required.
A group G from a class F is said to be recognizable in F by κP(G)
(shortly, κP -recognizable in F) if every group H ∈ F with κP(H) =
κP(G) is isomorphic to G. In other words, G is κP -recognizable in F if
hF (G) = 1, where hF (G) is the (possibly infinite) number of pairwise
non-isomorphic groups H ∈ F with κP(H) = κP(G). We denote by S the
classes of all finite simple groups. In the sequel, we show that the simple
group L2(7) ∼= L3(2) is κP -recognizable group in class S, in other words
hS(L2(7)) = 1.
Theorem 1. The simple group L2(7) is κP -recognizable in the class S of
all finite simple groups, that is, hS(L2(7)) = 1.
Proof. Let G ∈ S with κP(G) = κP(L2(7)) = 284 · 328 · 740 (see [33,
Theorem 4.1]). We have to prove that G is isomorphic to L2(7). Clearly, G
is nonabelian, since otherwise G ∼= Zp for some prime p, and so κP(G) =
κP(Zp) = pp−2, which is a contradiction. Now, we claim that π(G) ⊆
{2, 3, 5, 7}. Suppose p ∈ π(G) and p > 11. Let cp be the number of cyclic
subgroups of order p in G. By Lemma 6, cp > p + 1, because G is a
nonabelian simple group. Therefore, from Lemma 5, we deduce that
κP(G) > κP(Zp)
cp > κP(Zp)
p+1 = p(p−2)(p+1)
> 11108 > κP(G),
which is a contradiction. This shows that π(G) ⊆ {2, 3, 5, 7}, as claimed.
“adm-n2” — 2021/7/19 — 10:26 — page 202 — #38
202 Properties of graphs associated with groups
By results collected in [64, Table 1],G is isomorphic to one of the groups
A5
∼= L2(4) ∼= L2(5), A6
∼= L2(9), S4(3) ∼= U4(2), L2(7) ∼= L3(2), L2(8),
U3(3),A7,L2(49),U3(5),L3(4),A8
∼= L4(2),A9, J2,A10,U4(3),S4(7),S6(2)
orO+
8 (2). In all cases, except A5 and L2(7),G contains a subgroup H which
is isomorphic to A6 (see [19]). But then, κP(G) > κP(H) = 2180 ·340 ·5108,
a contradiction. If G is isomorphic to A5, then κP(G) = 220 · 310 · 518,
which contradicts the assumption. Thus G is isomorphic to L2(7), as
required.
3.2. Power-free decompositions
A generalization of split graphs was introduced and investigated under
the name (m,n)-graphs in [9]. A graph Γ is an (m,n)-graph if its vertex
set can be partitioned into m cliques C1, . . . , Cm and n independent sets
I1, . . . , In. In this situation,
VΓ = C1 ⊎ C2 ⊎ · · · ⊎ Cm ⊎ I1 ⊎ I2 ⊎ · · · ⊎ In,
is called an (m,n)-split partition of Γ. Thus, (m,n)-graphs are a natural
generalization of split graphs, which are precisely (1, 1)-graphs.
Accordingly, we are motivated to make the following definition.
Definition 1. Let G be a group and n > 1 an integer. We say that G
has an n-power-free decomposition if it can be partitioned as a disjoint
union of a cyclic p-subgroup C of maximal order and n nonempty subsets
B1, B2, . . . , Bn:
G = C ⊎B1 ⊎B2 ⊎ · · · ⊎Bn, (2)
such that the Bi’s are independent sets in P(G) and |Bi| > 1, for each i.
If n = 1, we simply say G = C ⊎B1 is a power-free decomposition of G.
Since C is a cyclic p-subgroup of maximal order in Definition 1, C is
a clique, and so Eq (2) is a (1, n)-split partition of P(G). Note that, there
are some finite groups which do not have an n-power-free decomposition,
for any n, for example one can consider cyclic groups (see Proposition 1).
On the other hand, the structure of groups G which have a power-free
decomposition is obtained (see Theorem 2).
Lemma 8. Suppose G has an n-power-free decomposition:
G = C ⊎B1 ⊎B2 ⊎ · · · ⊎Bn,
where C is a cyclic p-subgroup of G. Then the following statements hold:
“adm-n2” — 2021/7/19 — 10:26 — page 203 — #39
X. Chen, A. Moghaddamfar, M. Zohourattar 203
(a) If b ∈ G \ C, then φ(o(b)) 6 n. In particular, we have
π(G) ⊆ π((n+ 1)!) ∪ {p}.
(b) If p /∈ π((n+1)!), then C is normal and CC(b) = 1 for each b ∈ G\C.
In particular, Z(G) = 1.
(c) The set of universal vertices of P(G) is contained in C.
Proof. (a) The first statement follows immediately from the fact that the
set of generators of cyclic group 〈b〉, which has φ(o(b)) elements, forms a
complete set in the P(G,G \ C), and hence each Bi contains at most one
of the generators. The second statement is also clear, because for each
q ∈ π(G) \ {p}, there exists an element b ∈ G \ C of order q, and so by
first part φ(q) = q − 1 6 n, or q 6 n+ 1.
(b) Assume the contrary. Let C = 〈x〉 with o(x) = pm > 1. Then, there
exists b ∈ G\C such that xb /∈ C. By part (a) it follows that φ(o(xb)) 6 n.
Since o(xb) = o(x),
φ(o(xb)) = φ(o(x)) = φ(pm) = pm−1(p− 1),
and so we obtain
p− 1 6 pm−1(p− 1) 6 n.
This forces p 6 n+ 1, which contradicts the hypothesis.
Let b ∈ G \ C. Suppose c in C is not the identity and commutes
with b. Replacing b by an appropriate power, we may assume without
loss that p divides o(bc). Thus, we conclude that p− 1 divides φ(o(bc)).
Since bc ∈ G \ C, by part (a) we have φ(o(bc)) 6 n. Thus, it follows
that p− 1 6 n, which is a contradiction. This shows that CC(b) = 1, as
required.
(c) It is clear from Definition 1.
As the following result shows that there are some examples of groups
for which there does not exist any n-power-free decomposition.
Proposition 1. Any cyclic group has no n-power-free decomposition.
Proof. Assume the contrary and let G = 〈x〉 be a cyclic group with an
n-power-free decomposition:
G = C ⊎B1 ⊎B2 ⊎ · · · ⊎Bn,
“adm-n2” — 2021/7/19 — 10:26 — page 204 — #40
204 Properties of graphs associated with groups
for some n > 1, where C ⊂ G is a cyclic p-subgroup. Clearly, x is a
universal vertex in P(G), and so by Lemma 8 (c), x ∈ C. But then C = G,
which is a contradiction. The proof is complete.
Proposition 2. The generalized quaternion group Q2n, n > 3, has a
2-power-free decomposition.
Proof. With the following presentation:
Q2n = 〈x, y | x2
n−1
= 1, y2 = x2
n−2
, xy = x−1〉,
we may choose C = 〈x〉, and
B1 = {y, xy, . . . , x2
n−2−1y}, B2 = {x2
n−2
y, x2
n−2+1y, . . . , x2
n−1−1y}.
Then Q2n = C ⊎ B1 ⊎ B2 is a 2-power-free decomposition, and this
completes the proof.
Given a group G, 1 ∈ G is a universal vertex of the power graph P(G).
Now, as an immediate corollary of Lemma 4 and Propositions 1 and 2,
we have the following.
Corollary 2. Let G be a group, S the set of universal vertices of the power
graph P(G), and |S| > 1. Then G has an n-power-free decomposition iff
G is isomorphic to a generalized quaternion group.
Theorem 2. The following conditions on a group G are equivalent:
(a) G has a power-free decomposition, G = C ⊎B, where C is a cyclic
p-subgroup of G.
(b) One of the following statements holds:
(1) p = 2 and G is an elementary abelian 2-group of order > 4.
(2) p = 2 and G is the dihedral group D2m of order 2m, for some
integer m > 3.
(3) p > 2 and G is the dihedral group D2pn (a Frobenius group) of
order 2pn with a cyclic kernel of order pn.
Proof. (a) ⇒ (b). Suppose G = C ⊎B is a power-free decomposition of G,
where C ⊂ G is a cyclic p-subgroup of maximal order. It follows by Lemma
8 (a) that every element b ∈ B is an involution, and also |G| = 2mpn, for
some odd prime p and m > 1, n > 0. We shall treat the cases n = 0 and
n > 1, separately.
Case 1. n = 0. In this case, G is a 2-group. If |C| 6 2, then G is
an elementary abelian 2-group and (1) holds. We may now assume that
“adm-n2” — 2021/7/19 — 10:26 — page 205 — #41
X. Chen, A. Moghaddamfar, M. Zohourattar 205
|C| > 2. Put C = 〈x〉. Then, for every b in B, xb is not an involution and
so xb ∈ C, which shows that C is a normal subgroup of G. Thus G/C is
an elementary abelian 2-group by the previous paragraph.
We now claim that [G : C] = 2. To prove this, we assume that
[G : C] = 2t, where t > 2. Let I = Inv(G) be the set of involutions of G.
Then, we have I = B ∪ {z}, where z is the unique involution in C, and so
|I| = |B|+1 = |G|−|C|+1 = |G|−
|G|
2t
+1 =
(
2t − 1
2t
)
|G|+1 >
3
4
|G|+1,
which forces G to be an abelian group. We recall that, a finite group is
abelian if at least 3/4 of its elements have order two. But then, if b ∈ B,
then bx is not an involution and also bx /∈ C, which is a contradiction.
Let b be an involution in B. Then G = 〈x, b〉. Since bx ∈ B, bx is an
involution, and thus bxb = x−1, which implies that G is a dihedral group
and (2) follows.
Case 2. n > 1. In this case, |G| = 2mpn where m,n > 1, and C is a
cyclic p-group of maximal order. As in previous case C = 〈x〉 is a normal
subgroup of G and G/C is an elementary abelian 2-group. Note that, G
does not contain an element of order 2p, and so C = CG(C). Moreover,
since
G/C = NG(C)/CG(C) →֒ Aut(C),
and Aut(C) is a cyclic group of order φ(pn) = pn−1(p− 1), we conclude
that |G/C| = 2. Therefore, if b is an involution in G, then
G = 〈x, b〉 = 〈x〉⋊ 〈b〉,
and since b acts on 〈x〉 fixed-point-freely, G is a Frobenius group of order
2pn with cyclic kernel C of order pn, and (3) follows.
(b) ⇒ (a). Obviously.
3.3. Commuting graphs
In this section, we consider the problem of finding the tree-number of
the commuting graphs associated with a family of finite simple groups. The
Suzuki groups Sz(q), an infinite series of simple groups of Lie type, were
defined in [61,62] as subgroups of the groups L4(q), with q = 22n+1 > 8. In
what follows, we shall give an explicit formula for κC(Sz(q)). Let G = Sz(q),
where q = 22n+1. We begin with some well-known facts about the simple
group G. These results have been obtained by Suzuki [61,62]:
“adm-n2” — 2021/7/19 — 10:26 — page 206 — #42
206 Properties of graphs associated with groups
(1) Let r = 2n+1. Then |G| = q2(q−1)(q2+1) = q2(q−1)(q−r+1)(q+
r + 1), and µ(G) = {4, q − 1, q − r + 1, q + r + 1}. For convenience,
we write αq = q − r + 1 and βq = q + r + 1.
(2) Let P be a Sylow 2-subgroup of G. Then P is a 2-group of order q2
with exp(P ) = 4, which is a TI-subgroup, and |NG(P )| = q2(q − 1).
(3) Let A ⊂ G be a cyclic subgroup of order q − 1. Then A is a TI-
subgroup and the normalizer NG(A) is a dihedral group of order
2(q − 1).
(4) Let B ⊂ G be a cyclic subgroup of order αq. Then B is a TI-subgroup
and the normalizer NG(B) has order 4αq.
(5) Let C ⊂ G be a cyclic subgroup of order βq. Then C is a TI-subgroup
and the normalizer NG(C) has order 4βq.
We recall that, in general, a subgroup H 6 G is a TI-subgroup (trivial
intersection subgroup) if for every g ∈ G, either Hg = H or H ∩Hg = {1}.
Lemma 9. κC(P ) = 2(q−1)2q(q
2+q−3).
Proof. By Theorem VIII.7.9 of [29] and Lemma XI.11.2 of [30], Z(P ) is
an elementary abelian 2-group of order q and every element outside Z(P )
has order 4. Observe that P is the centralizer in G of all of the nontrivial
elements of Z(P ). If x ∈ P \ Z(P ), then 〈Z(P ), x〉 6 CG(x). In the proof
of Lemma XI.11.7 of [30], we see that the elements of order 4 in G lie in
two conjugacy classes. This implies that |CG(x)| = 2|Z(P )|, from which
we deduce that CG(x) = 〈Z(P ), x〉. Then for all x, y ∈ P \ Z(P ) either
CG(x) = CG(y) or CG(x)∩CG(y) = Z(P ). Hence, {CG(x)|x ∈ P \Z(P )}
forms a partition of P for which the intersection of pairwise centralizers
is Z(P ). This shows that
C(P ) = Kq ∨ (Kq ⊕Kq ⊕ · · · ⊕Kq
︸ ︷︷ ︸
q−1
).
Moreover, by Lemma 1, the eigenvalues of Laplacian matrix LC(P ) are:
q2, q2, q2, . . . , q2
︸ ︷︷ ︸
q−1
, 2q, 2q, . . . , 2q
︸ ︷︷ ︸
(q−1)2
, q, q, . . . , q
︸ ︷︷ ︸
q−2
, 0.
It follows immediately using Eq. (1) that
κC(P ) = 2(q−1)2q(q
2+q−3),
as required.
“adm-n2” — 2021/7/19 — 10:26 — page 207 — #43
X. Chen, A. Moghaddamfar, M. Zohourattar 207
Theorem 3. Let q = 22n+1, where n > 1 is an integer. Then, we have
κC(Sz(q)) =
(
2(q−1)2q(q
2+q−3)
)q2+1
(q − 1)(q−3)a(αq)
(αq−2)b(βq)
(βq−2)c,
where a = q2(q2 + 1)/2, b = q2(q − 1)βq/4 and c = q2(q − 1)αq/4.
Proof. Let G = Sz(q), where q = 22n+1 > 8. As already mentioned, G
contains a Sylow 2-subgroup P of order q2 and cyclic subgroups A, B, and
C, of orders q − 1, αq and βq, respectively. Moreover, every two distinct
conjugates of them intersect trivially and every element of G is a conjugate
of an element in P ∪A ∪B ∪ C. Looking at the proof of Lemma 11.6, we
see that the cyclic subgroups A, B, and C, are the centralizers of their
nonidentity elements, while P is the centralizer in G of all of the nontrivial
elements of Z(P ). Let
G = NPx1 ∪ · · · ∪NPxp = NAy1 ∪ · · · ∪NAya
= NBz1 ∪ · · · ∪NBzb = NCt1 ∪ · · · ∪NCtc,
be coset decompositions of G by NP = NG(P ), NA = NG(A), NB =
NG(B) and NC = NG(C), where p = [G : NP ] = q2 + 1, a = [G :
NA] = q2(q2 + 1)/2, b = [G : NB] = q2(q − 1)βq/4 and c = [G : NC ] =
q2(q − 1)αq/4. Then, we have
G = P x1 ∪ · · · ∪ P xp ∪Ay1 ∪ · · · ∪Aya ∪Bz1 ∪ · · · ∪Bzb ∪Ct1 ∪ · · · ∪Ctc .
This shows that
C(G) = K1 ∨
(
p C(P#)⊕ aC(A#)⊕ bC(B#)⊕ c C(C#)
)
= K1 ∨
(
p C(P#)⊕ aK(q−1)−1 ⊕ bKαq−1 ⊕ cKβq−1
)
,
and so
κC(G) = κC(P )p · κC(Kq−1)
a · κC(Kαq)
b · κC(Kβq
)c.
Now, Lemma 9 and Cayley’s formula yield the result.
References
[1] J. H. Abawajy, A. V. Kelarev and M. Chowdhury, Power graphs: a survey, Electron.
J. Graph Theory Appl. (EJGTA), 1(2) (2013), 125–147.
[2] N. Akbari and A. R. Ashrafi, Note on the power graph of finite simple groups,
Quasigroups Related Systems, 23(2) (2015), 165–173.
“adm-n2” — 2021/7/19 — 10:26 — page 208 — #44
208 Properties of graphs associated with groups
[3] A. Ballester-Bolinches, J. Cossey and R. Esteban-Romero, A characterization via
graphs of the soluble groups in which permutability is transitive, Algebra Discrete
Math., 8(4)(2009), 10–17.
[4] S. Bera, On the intersection power graph of a finite group, Electron. J. Graph
Theory Appl. (EJGTA), 6(1) (2018), 178–189.
[5] S. Bera and A. K. Bhuniya, On enhanced power graphs of finite groups, J. Algebra
Appl., 17 (8)(2018), 1850146, 8 pp.
[6] A. K. Bhuniya and S. Bera, Normal subgroup based power graphs of a finite group,
Comm. Algebra, 45(8) (2017), 3251–3259.
[7] A. K. Bhuniya and S. Bera, On some characterizations of strong power graphs of
finite groups, Spec. Matrices, 4 (2016), 121–129.
[8] N. Biggs, Algebraic Graph Theory, Cambridge University Press, London, 1974.
[9] A. Brandstädt, Partitions of graphs into one or two independent sets and cliques,
Discrete Math., 152(1-3) (1996), 47–54.
[10] J. R. Britnell and N. Gill, Perfect commuting graphs, J. Group Theory, 20(1)
(2017), 71-—102.
[11] D. Bubboloni, M. A. Iranmanesh, S. M. Shaker. Quotient graphs for power graphs,
Rend. Semin. Mat. Univ. Padova, 138 (2017), 61–89.
[12] P. J. Cameron, The power graph of a finite group. II, J. Group Theory, 13(6)
(2010), 779–783.
[13] P. J. Cameron, H. Guerra and S. Jurina, The power graph of a torsion-free group,
J. Algebraic Combin., 49(1) (2019), 83–98.
[14] I. Chakrabarty, S. Ghosh and M. K. Sen, Undirected power graphs of semigroups,
Semigroup Forum, 78 (2009), 410–426.
[15] S. Chattopadhyay and P. Panigrahi, Some structural properties of power graphs
and k-power graphs of finite semigroups, J. Discrete Math. Sci. Cryptogr., 20(5)
(2017), 1101–1119.
[16] S. Chattopadhyay and P. Panigrahi, Some relations between power graphs and
Cayley graphs, J. Egyptian Math. Soc., 23(3) (2015), 457–462.
[17] S. Chattopadhyay and P. Panigrahi, Connectivity and planarity of power graphs
of finite cyclic, dihedral and dicyclic groups, Algebra Discrete Math., 18(1) (2014),
42–49.
[18] S. Chattopadhyay, P. Panigrahi and F. Atik, Spectral radius of power graphs on
certain finite groups, Indag. Math. (N.S.), 29(2) (2018), 730–737.
[19] J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker and R. A. Wilson R A,
Atlas of Finite Groups, Oxford Clarendon Press, 1985.
[20] B. Curtin, G. R. Pourgholi and H. Yousefi-Azari, On the punctured power graph
of a finite group, Australas. J. Combin., 62 (2015), 1–7.
[21] A. K. Das and D. Nongsiang, On the genus of the commuting graphs of finite
nonabelian groups, Int. Electron. J. Algebra, 19 (2016), 91–109.
[22] A. Doostabadi and M. Farrokhi D. G., Embeddings of (proper) power graphs of
finite groups, Algebra Discrete Math., 24(2) (2017), 221–234.
“adm-n2” — 2021/7/19 — 10:26 — page 209 — #45
X. Chen, A. Moghaddamfar, M. Zohourattar 209
[23] A. Doostabadi, M. Farrokhi D. Ghouchan, On the connectivity of proper power
graphs of finite groups, Comm. Algebra, 43(10) (2015), 4305–4319.
[24] S. Földes and P. L. Hammer, Split graphs, Proceedings of the Eighth Southeastern
Conference on Combinatorics, Graph Theory and Computing (Louisiana State
Univ., Baton Rouge, La., 1977), 311––315.
[25] A. Hamzeh, Signless and normalized Laplacian spectrums of the power graph
and its supergraphs of certain finite groups, J. Indones. Math. Soc., 24(1) (2018),
61–69.
[26] A. Hamzeh and A. R. Ashrafi,The order supergraph of the power graph of a finite
group, Turkish J. Math., 42(4) (2018), 1978–1989.
[27] A. Hamzeh and A. R. Ashrafi, Spectrum and L-spectrum of the power graph and
its main supergraph for certain finite groups, Filomat, 31(16) (2017), 5323–5334.
[28] A. Hamzeh and A. R. Ashrafi, Automorphism groups of supergraphs of the power
graph of a finite group, European J. Combin., 60 (2017), 82–88.
[29] B. Huppert and N. Blackbrun, Finite Groups II, Springer-Verlag, Berlin, 1982.
[30] B. Huppert and N. Blackbrun, Finite Groups III, Springer-Verlag, Berlin, 1982.
[31] S. H. Jafari, Some results in a new power graphs in finite groups, Util. Math., 103
(2017), 181–187.
[32] S. H. Jafari, Some properties of power graphs in finite group, Asian-Eur. J. Math.,
9 (4)(2016), 1650079, 6 pp.
[33] S. Kirkland, A. R. Moghaddamfar, S. Navid Salehy, S. Nima Salehy and M.
Zohourattar, The complexity of power graphs associated with finite groups, Con-
tributions to Discrete Mathematics, 13(2)(2018), 124–136.
[34] A. V. Kelarev, Graph Algebras and Automata, Marcel Dekker, New York, 2003.
[35] A. V. Kelarev, Ring Constructions and Applications, World Scientific, River Edge,
NJ, 2002.
[36] A. V. Kelarev and S. J. Quinn, A combinatorial property and power graphs of
groups, The Vienna Conference, Contrib. General Algebra, 12 (2000), 229–235.
[37] A. V. Kelarev and S. J. Quinn, Directed graphs and combinatorial properties of
semigroups, J. Algebra, 251 (2002), 16–26.
[38] A. V. Kelarev and S. J. Quinn, A combinatorial property and power graphs of
semigroups, Comment. Math. Univ. Carolinae, 45 (2004), 1–7.
[39] A. V. Kelarev, S. J. Quinn and R. Smolikova, Power graphs and semigroups of
matrices, Bull. Austral. Math. Soc., 63 (2001), 341–344.
[40] A. Kelarev, J. Ryan, J. Yearwood, Cayley graphs as classifiers for data mining:
The influence of asymmetries, Discrete Mathematics, 309 (2009), 5360–5369.
[41] X. Ma and M. Feng, On the chromatic number of the power graph of a finite
group, Indag. Math. (N.S.), 26(4) (2015), 626–633.
[42] X. Ma, M. Feng and K. Wang, The rainbow connection number of the power graph
of a finite group, Graphs Combin., 32(4) (2016), 1495–1504.
[43] X. Ma, R. Fu and X. Lu, On the independence number of the power graph of a
finite group, Indag. Math. (N.S.), 29(2) (2018), 794–806.
“adm-n2” — 2021/7/19 — 10:26 — page 210 — #46
210 Properties of graphs associated with groups
[44] X. Ma, R. Fu, X. Lu, M. Guoand Z. Zhao, Perfect codes in power graphs of finite
groups, Open Math., 15 (2017), 1440–1449.
[45] A. Mahmoudifar and A. R. Moghaddamfar, Commuting graphs of groups and
related numerical parameters, Comm. Algebra, 45(7)(2017), 3159–3165.
[46] S. K. Maity, Bipartite and planar power graphs of finite groups, Southeast Asian
Bull. Math., 39(4) (2015), 539–543.
[47] Z. Mehranian, A. Gholami and A. R. Ashrafi, The spectra of power graphs of
certain finite groups, Linear Multilinear Algebra, 65(5) (2017), 1003–1010.
[48] Z. Mehranian, A. Gholami and A. R. Ashrafi, A note on the power graph of a
finite group, Int. J. Group Theory, 5(1) (2016), 1–10.
[49] R. Merris, Laplacian graph eigenvectors, Linear Algebra Appl., 278 (1998), 221–236.
[50] A. R. Moghaddamfar, S. Rahbariyan, S. Navid Salehy and S. Nima Salehy, The
number of spanning trees of power graphs associated with specific groups and
some applications, Ars Combinatoria, 113 (2017), 269–296.
[51] A. R. Moghaddamfar, S. Rahbariyan, and W. J. Shi, Certain properties of the
power graph associated with a finite group, J. Algebra Appl., 13(7) (2014), 1450040,
18 pp.
[52] R. P. Panda and K. V. Krishna, On the minimum degree, edge-connectivity
and connectivity of power graphs of finite groups, Comm. Algebra, 46(7) (2018),
3182–3197.
[53] R. P. Panda and K. V. Krishna, On connectedness of power graphs of finite groups,
J. Algebra Appl., 17(10) (2018), 1850184, 20 pp.
[54] K. Pourghobadi and S. H. Jafari, The diameter of power graphs of symmetric
groups, J. Algebra Appl., 17(12) (2018), 1850234, 11 pp.
[55] G. R. Pourgholi, H. Yousefi-Azari and A. R. Ashrafi, The undirected power graph
of a finite group, Bull. Malays. Math. Sci. Soc., 38(4) (2015), 1517–1525.
[56] I. V. Protasov and K. D. Protasova, Automorphisms of kaleidoscopical graphs,
Algebra Discrete Math., 6(2)(2007), 125–129.
[57] H. Sachs, On the number of spanning trees, Proceedings of the Fifth British Com-
binatorial Conference (Univ. Aberdeen, Aberdeen, 1975), pp. 529–535. Congressus
Numerantium, No. XV, Utilitas Math., Winnipeg, Man., 1976.
[58] M. Shaker and M. A. Iranmanesh, On groups with specified quotient power graphs,
Int. J. Group Theory, 5(3) (2016), 49–60.
[59] Y. Shitov, Coloring the power graph of a semigroup, Graphs Combin., 33(2) (2017),
485–487.
[60] A. J. Slupik and V. I. Sushchansky, Minimal generating sets and Cayley graphs of
Sylow p-subgroups of finite symmetric groups, Algebra Discrete Math., 8(4)(2009),
167–184.
[61] M. Suzuki, A new type of simple groups of finite order, Proc. Nat. Acad. Sci.
U.S.A., 46 (1960), 868–870.
[62] M. Suzuki, On a class of doubly transitive groups, Ann. of Math., 75 (1) (1962),
105–145.
“adm-n2” — 2021/7/19 — 10:26 — page 211 — #47
X. Chen, A. Moghaddamfar, M. Zohourattar 211
[63] T. Tamizh Chelvam and M. Sattanathan, Power graph of finite abelian groups,
Algebra Discrete Math., 16(1) (2013), 33–41.
[64] A. V. Zavarnitsine, Finite simple groups with narrow prime spectrum, Sib. Elektron.
Mat. Izv., 6 (2009), 1–12.
Contact information
Xiaoyou Chen School of Sciences, Henan University of
Technology, 450001, Zhengzhou, China
E-Mail(s): cxy19800222@163.com
Ali Reza
Moghaddamfar,
Mahsa Zohourattar
Faculty of Mathematics, K. N. Toosi University
of Technology, P.O. Box 16315-1618, Tehran,
Iran
E-Mail(s): moghadam@kntu.ac.ir,
zohoorattar@mail.kntu.ac.ir
Web-page(s): https:
//wp.kntu.ac.ir/moghadam/
Received by the editors: 06.06.2018
and in final form 04.03.2019.
|