Electronic Journal of Graph Theory and Applications 10 .
, 89Ae111 A survey on enhanced power graphs of finite Xuanlong Maa .
Andrei Kelarevb .
Yuqing Linb .
Kaishun Wangc School of Science.
XiAoan Shiyou University.
XiAoan 710065.
China b Discipline of Computing & Information Technology.
School of Information & Phys.
Sci.
College of Engi- neering.
Science and Environment.
The University of Newcastle.
Callaghan, 2308.
NSW.
Australia c Lab.
of Math.
& Complex Systems (MOE).
School of Math.
Sci.
Beijing Normal University.
Beijing 100875.
China xuanlma@mail.
cn, andrei.
kelarev@gmail.
com, yuqing.
lin@newcastle.
au, wangks@bnu.
Abstract We survey known results on enhanced power graphs of finite groups.
Open problems, questions and suggestions for future work are also included.
Keywords: enhanced power graph, domination, metric dimension, perfect graph, forbidden subgraphs Mathematics Subject Classification: 05C25, 05C38, 05C40, 05C60, 05C12 DOI: 10.
5614/ejgta.
Introduction The study of graphical representations of algebraic structures, especially groups, has been an energizing and fascinating research area originating from the pioneering paper by Arthur Cayley .
with many recent results .
, 14, 40, 54, .
In particular, graphs associated to groups and other algebraic constructions have valuable applications .
, .
) and are related to automata theory .
The majority of these types of graphs have natural associated labelings.
Therefore, this direction can also be considered as a part of the broader field of research Ae the investigation of graph labelings.
For more information, refer to examples of publications devoted to graph labelings (.
, 46, 57, 66, .
Received: 26 August 2021.
Revised: 18 December 2021.
Accepted: 23 December 2021.
A survey on enhanced power graphs of finite groups Xuanlong Ma et al.
The power graphs of groups are a fairly recent development in the realm of graphs from groups.
The power graph of a group was introduced by Kelarev and Quinn .
For a group G, the directed Ie Oe power graph of G is denoted by P (G) and is defined as a digraph with vertex set G and there is a directed edge from x to y, for x, y OO G, x 6= y, if and only if y is a power of x, i.
, y = xk for some integer k, which is also equivalent to saying that y belongs to the subgroup hxi generated by x in G.
The power graphs of semigroups were investigated in .
, 51, .
All the above papers .
, 50, 51, .
use the brief term Aupower graphsAy to refer to the directed power graphs.
In 2009.
Chakrabarty et al.
explored the undirected power graphs of semigroups.
The undirected power graph P(G) of a group G coincides with the underlying undirected graph of the directed power graph defined in .
It has the vertex set G where two distinct elements are adjacent if one of them is a power of the other.
Cameron et al.
, .
examined the undirected power graphs of finite groups and initiated the use of the brief term Aupower graphAy with the second meaning of an undirected power graph.
Notice that the survey .
introduced the most general definition of a power graph defined for all power-associative magmas, i.
, sets with a power-associative operation (Definition 1 on p.
It is well known that magmas play essential roles in symbolic computation .
, 77, .
Let us refer to two surveys .
, .
for more information pertaining to the research results and open problems on the power graphs of groups.
Enhanced power graphs are another important class of graphs that have been actively investigated recently.
The term enhanced power graph of a group was introduced by Aalipour et al.
as a graph Aulying in betweenAy the power graph and the commuting graph, where the commuting graph of a group G, denoted by C(G), is the graph whose vertex set is G, and two distinct elements x, y are adjacent if xy = yx.
The enhanced power graph of a group G is denoted by Pe (G) and is defined as a simple graph with vertex set consisting of all elements of G, where two distinct vertices x, y are adjacent if and only if hx, yi is a cyclic subgroup of G.
The commuting graph was introduced by Brauer and Fowler in their seminal paper .
establishing that only finitely many groups of even order can have a prescribed centraliser.
The commuting graph is the complement of the non-commuting graph, first considered by Paul ErdoOs .
, .
Likewise, the enhanced power graph is the complement of the noncyclic graph, introduced in .
, .
A noncyclic graph of a group G is the graph, where two vertices x and y are adjacent if hx, yi is noncyclic.
For technical reasons, the papers .
, .
excluded isolated vertices from consideration.
Several papers also call the enhanced power graph using the terms cyclic graph or the deleted enhanced power graph, if the vertex corresponding to the identity of the group is deleted .
, 32, .
Clearly, for any group G, we have E(P(G)) OI E(Pe (G)) OI E(C(G)).
As a concrete example, we display the power graph and the enhanced power graph of abelian group Z2 yZ6 in Fig.
Note that C(Z2 y Z6 ) is a complete graph.
Many researchers have contributed to the understanding of enhanced power graphs of groups, especially after the publication of .
, and many interesting new theorems have appeared in the literature recently.
The present article is a survey of the results on enhanced power graphs of finite Various questions, open problems and suggestions for future work are also included.
This is the first survey devoted to the enhanced power graphs of finite groups.
A survey on enhanced power graphs of finite groups Xuanlong Ma et al.
, .
, .
, .
, .
, .
, .
, .
, .
, .
, .
, .
, .
, .
, .
, .
, .
, .
, .
, .
, .
, .
, .
, .
, .
Figure 1.
P(Z2 y Z6 ).
Pe (Z2 y Z6 ).
Outline of the paper This survey is divided into the following sections.
Section 2 presents the results on the groups with dominatable enhanced power graphs, which derive from an open problem in .
Section 3 describes the metric dimension and strong metric dimension of an enhanced power graph.
The exact values of these dimensions are computed for the enhanced power graphs of abelian groups, dihedral, semidihedral groups, and generalized quaternion groups.
Section 4 deals with the perfect enhanced power graphs of groups.
It gives a complete characterization of nilpotent groups that have perfect enhanced power graphs and also gives some groups whose enhanced power graphs are perfect.
Section 5 is devoted to the forbidden subgraphs of enhanced power graphs.
It presents a classification of all finite groups whose enhanced power graphs are split and threshold, and also classifies all finite nilpotent groups whose enhanced power graphs are chordal graphs and cographs.
Several families of non-nilpotent groups whose enhanced power graphs are chordal graphs and cographs are also included.
Section 6 contains the results on enhanced power graphs and other related graphs .
uch as power graphs and commuting graph.
Section 7 presents relevant results related to miscellaneous properties of the enhanced power graphs, including vertex connectivity, diameter, connectedness, clique number.
Eulerian graphs, and so on.
Section 8 deals with open problems, questions and conjectures on enhanced power graphs.
The paper concludes with a brief overview of other related work supplementing the presented results.
Terminology and notation A graph is a pair (V.
E), where V is a set with elements called vertices and E is a set of edges, , unordered pairs of vertices.
As usual, for a graph e, we use V .
and E.
to denote its vertex and edge sets, respectively.
The cardinality |V .
| is called the order of e.
The degree of u in e, denoted by de .
= d.
, is defined as the number of edges of e incident to u.
A graph is simple if it has no loops or parallel edges.
Likewise, a digraph can be defined by specifying a set of vertices and a collection of ordered pairs of vertices.
Each ordered pair .
, .
in the collection is called an arc .
r a directed edg.
from A survey on enhanced power graphs of finite groups Xuanlong Ma et al.
u to v.
The underlying graph of a digraph is the simple undirected graph obtained by replacing each arc by an edge with the same end-vertices.
All groups considered in this survey are finite.
Throughout the paper, unless stated otherwise, the word AographAo means a finite undirected graph without loops and multiple edges.
The distance between two vertices u and v in a graph e, denoted by de .
, .
= d.
, .
, is defined as the length of a shortest path between them in e.
Note that de .
, .
= 0 if u = v.
The diameter of e, denoted by diam.
, is the maximum distance between two vertices of G.
The strong product e OI of two graphs e and OI is the graph with vertex set V .
y V (OI) in which .
, .
, .
are adjacent if and only if one of u = x and vy OO E(H), v = y and ux OO E(G), and ux OO E(G) and vy OO E(H) holds.
An automorphism of a graph e is a permutation of V .
which maps adjacent vertices to adjacent vertices and nonadjacent vertices to nonadjacent vertices.
The automorphism group of e, denoted by Aut.
, is the group of automorphisms of e under the usual composition of permutations.
The vertex connectivity of a graph e, denoted by .
, is the minimum number of vertices which need to be removed from the vertex set of e so that the induced subgraph of e on the remaining vertices is disconnected.
Let e and OI be graphs.
The graph e is said to be OI-free if e has no induced subgraph isomorphic to OI.
A graph is a star if it is a tree with n vertices in which one vertex has degree n Oe 1 and every other vertex has degree 1.
Denote by Pn .
Cn , and Kn the path with n vertices, the cycle of length n, and the complete graph of order n, respectively.
The symbol 2K2 denotes the bipartite graph with four vertices and two disjoint edges.
An edge colouring or edge labeling of e is an assignment of some colours or labels to the edges of e.
An edge colouring of a graph is called a rainbow colouring if every pair of distinct vertices of the graph is connected by at least one path with no two edges sharing the same colour.
The rainbow connection number of e, denoted by rc.
, is the minimum positive integer k for which there exists a rainbow colouring with k colours in e.
A vertex of a graph e is called a dominating vertex if this vertex is adjacent to every other vertex of e.
The vertex set of e is denoted by V .
, and the edge set is E.
The distance between two vertices x and y in e, denoted de .
, .
, is the length of a shortest path from x to y.
If the situation is unambiguous, we denote de .
, .
simply by d.
, .
The greatest distance between any two vertices in e is called the diameter of e.
A subset of V .
is called a clique if any two distinct vertices in this subset are adjacent in e.
The clique number of e, denoted by O.
, is the maximum cardinality of a clique in e.
The chromatic number of a graph e, denoted by N.
, is the smallest number of colours for V .
so that adjacent vertices are coloured differently.
A graph is perfect if every induced subgraph has clique number equal to chromatic number.
A graph e is called weakly perfect if N.
= O.
We always use G to denote a finite group, and let e denote its identity element.
The order o.
of an element g of G is the cardinality of the cyclic subgroup hgi.
The set of orders of elements of G is denoted by Ae (G).
A maximal cyclic subgroup of G is a cyclic subgroup, which is not a proper subgroup of any other cyclic subgroup of G.
Denote by MG the set of all maximal cyclic subgroups of G.
Note that |MG | = 1 if and only if G is cyclic.
The cyclic group of order n is denoted by Zn .
A group G is said to be nilpotent if G has an upper central series that terminates with G.
Equivalently, its central series is of finite length or its lower central series terminates with .
It is well known that all finite p-groups and abelian groups are nilpotent.
It is well known that each finite nilpotent group is isomorphic to the direct product of its Sylow p-subgroups.
A survey on enhanced power graphs of finite groups Xuanlong Ma et al.
The alternating group of degree n, denoted by An , is the group of even permutations of a set of n elements.
For n Ou 3, the dihedral group of order 2n is denoted by D2n .
Recall that it is defined by the presentation D2n = ha, b : an = b2 = e, bab = aOe1 i.
Note that D2n = hai O .
, ab, a2 b, .
, anOe1 .
, o.
= 2 for any 1 O i O n, and MD2n = .
ai, habi, ha2 bi, .
, han b.
For m Ou 2, the generalized quaternion group Q4m of order 4m is given by Q4m = hx, y : xm = y 2 , x2m = e, y Oe1 xy = xOe1 i.
For any i O 1 O m and any x, y OO Q4m , it is well known that o.
m ) = 2, o.
= 4, xm OO OM OOMQ4m M , and MQ4m = .
xi, hxyi, hx2 yi, .
, hxm y.
Dominatable enhanced power graphs The concept of domination is very important in graph theory.
Recently, it has been considered, for example, in .
, 18, 37, 42, 45, 58, .
It is obvious that the identity element e is a dominating vertex of every enhanced power graph Pe (G).
Bera and Bhuniya .
defined a dominatable enhanced power graph as an enhanced power graph with a dominating vertex other than e.
For example.
Pe (Z2 y Z6 ) is a dominatable, since .
, .
is a dominating vertex .
ee Fig.
In .
, the authors characterized all abelian groups and all p-groups G such that Pe (G) is Theorem 2.
Theorem 3.
) Let G be a group and n OO N.
If gcd(|G|, .
= 1, then the enhanced power graph Pe (G y Zn ) is dominatable.
Theorem 2.
Theorem 3.
) Let G be a abelian group.
Then Pe (G) is dominatable if and only if G has a cyclic Sylow subgroup.
Theorem 2.
Theorem 3.
) Let G be a non-abelian p-group.
Then the enhanced power graph Pe (G) is dominatable if and only if G is a generalized quaternion group.
Ma and She .
gave a characterization of dominatable enhanced power graphs using the following concepts.
For x OO G, the cyclicizer .
of x in G, denoted by Cyc.
, is defined by Cyc.
= .
OO G : hx, yi is cycli.
The cycel of G, denoted by K(G), is defined by K(G) = OxOOG Cyc.
By .
Theorem .
K(G) = OM OOMG M is a normal subgroup of G.
Theorem 2.
Theorem 4.
) Let G be a group.
Then Pe (G) is dominatable if and only if K(G) is nontrivial.
Since K(G) is a normal subgroup of G, the above theorem yields the following result.
A survey on enhanced power graphs of finite groups Xuanlong Ma et al.
Corollary 2.
Theorem 3.
) Let G be a non-abelian simple group.
Then Pe (G) is not In .
, the authors characterized all finite nilpotent groups with dominatable enhanced power This result extends .
Theorems 3.
2 and 3.
Theorem 2.
Proposition 4.
) Let G be a nilpotent group.
Then Pe (G) is dominatable if and only if GO = Q4A2n y H or Zpn y K, where n Ou 1, p is a prime, and H and K are nilpotent groups with 2 - |H| and p - |K|.
Theorem 2.
Proposition 4.
) .
For n Ou 3.
Pe (D2n ) is not dominatable.
For m Ou 2.
Pe (Q4m ) is dominatable.
Recently.
Mahmoudifar & Babai .
gave another characterization for finite groups with dominatable enhanced power graphs.
Theorem 2.
Main theore.
) Let G be a finite group.
Then Pe (G) is dominatable if and only if there exists a prime p such that p | |Z(G)| and every Sylow p-subgroup of G is isomorphic to either a cyclic group or a generalized quaternion group, where Z(G) is the center of G.
The above result implies that if G is a group with |Z(G)| = 1, then Pe (G) is not dominatable.
Theorem 2.
Corollary 3.
) Suppose that G is a non-abelian group of order pq, where p and q are distinct primes.
Then Pe (G) is not dominatable.
Theorem 2.
Theorem 3.
) Suppose that G = G1 yG2 yA A AyGr with gcd(|Gi |, |Gj |) = 1 for distinct indices i and j.
Then Pe (G) is dominatable if and only if there exists k OO .
, 2, .
, .
such that Pe (Gk ) is dominatable.
It was noted in .
that if G is a finite group such that all its proper subgroups are dominatable, then Pe (G) is not necessarily dominatable.
Also, if there exists a nontrivial normal subgroup N of G such that both N and the quotient group G/N are dominatable, then Pe (G) is not necessarily dominatable.
Moreover.
Pe (G) is dominatable if G is isomorphic to the special linear group SL.
, .
, where q Ou 3 is a natural power of an odd prime.
Theorem 2.
Corollary 3.
) If G is one of the following groups:
A non-abelian simple group.
The symmetric group Sn , where n Ou 3.
The projective general linear group PGL.
, .
, where n Ou 2.
A Frobenius group, then Pe (G) is not dominatable.
A survey on enhanced power graphs of finite groups Xuanlong Ma et al.
Metric dimension and strong metric dimension of enhanced power graphs Metric dimension was introduced by Harary and Melter .
and, independently, by Slater .
It is defined as follows.
A vertex z in a graph e is said to resolve a pair of distinct vertices x and y if d.
, .
6= d.
, .
A resolving set of e is a subset S of V .
such that every pair of distinct vertices of e is resolved by some vertex in S.
The metric dimension of e, denoted by dim.
, is the minimum cardinality of a resolving set of e.
It was considered, for example, in .
Strong metric dimension of a graph was introduced by SeboU and Tannier .
, in relation to the applications of strong resolving sets to combinatorial searching.
A vertex z of a graph e is said to strongly resolve vertices x and y in e, if there exists a shortest path from z to x containing y, or a shortest path from z to y containing x.
A subset S of V .
is a strong resolving set of e if every pair of vertices of e is strongly resolved by some vertex in S.
The smallest cardinality of a strong resolving set of e is denoted by sdim.
and is called the strong metric dimension of e.
The problem of computing strong metric dimension is NP-hard .
Ma and She .
gave an explicit formula for the metric dimension of the enhanced power graph of a group, using the following definition.
For x, y OO G, we write x O y if N .
= N .
or N .
= N .
in Ge (G).
Note that O is an equivalence relation.
Denote by x the O-class containing the vertex x OO G, and let G = .
: x OO G}.
Theorem 3.
Theorem 3.
) Let G be a group of order n.
Then dim(Pe (G)) = n Oe |G|.
As a corollary of Theorem 3.
1, the metric dimensions of the enhanced power graphs of an elementary abelian p-group, a dihedral group, and a generalized quaternion group have been determined in .
Corollary 3.
Example 3.
) .
Let k Ou 2 and p a prime.
Then 2k Oe 2, if p = 2, k pOe2 dim(Pe (Zp )) = pk Oe pOe1 , otherwise.
dim(Pe (D2n )) = 2n Oe 3.
dim(Pe (Q4m )) = 3m Oe 2.
Ma and Zhai .
characterized the strong metric dimension of the enhanced power graph of a finite group.
For x, y OO G, denote by OO the equivalence relation defined by N .
= N .
in Pe (G).
It is easy to see that OO is an equivalence relation over G.
The OO-class containing the element x OO G is denoted by x For a subset S of G and an element g OO G, let Sb = .
x : x OO S}.
Mg = {M OO MG : g OO M }.
Theorem 3.
Theorem 4.
) Let G be a group of order n.
Then .
: M OO MG } sdim(Pe (G)) = n Oe max{|M = n Oe max{|S| : S OI M OO MG and for any x, y OO S.
Mx 6= My }.
A survey on enhanced power graphs of finite groups Xuanlong Ma et al.
Panda et al.
and Dalal & Kumar .
computed sdim(Pe (G)) for some special groups G.
Theorem 3.
Corollarys 4.
6 and 4.
, .
Theorems 3.
15, 3.
, .
Theorem 3.
) .
sdim(Pe (G)) = |G| Oe 1 if and only if G is cyclic.
If G is a noncyclic P-group of order n, then sdim(Pe (G)) = n Oe 2.
sdim(Pe (D2n )) = 2n Oe 2.
sdim(Pe (Q4n )) = 4n Oe 2.
Let G be a noncyclic abelian p-group with order n and exponent pm .
Then sdim(Pe (G)) = n Oe m Oe 1.
For n Ou 1, the group U6n of order 6n is defined as the group generated by the elements a and b such that a2n = b3 = e, ba = abOe1 , that is U6n = ha, b : a2n = b3 = e, ba = abOe1 i.
Theorem 3.
Theorem 3.
) Let k and t be integers such that k Ou 0, t > 0 and 3 - t.
Then sdim(Pe (U6.
)) = 6.
Oe k Oe 2.
For n Ou 2, the semidihedral group SD8n is a group of order 8n defined by the presentation SD8n = ha, b : a4n = b2 = e, ba = a2nOe1 bi.
Theorem 3.
Theorem 3.
) sdim(Pe (SD8n )) = 8n Oe 3.
For a positive integer n, the group V8n of order 8n is defined by V8n = ha, b : a2n = b4 = e, ba = aOe1 bOe1 , bOe1 a = aOe1 bi.
Theorem 3.
Theorem 3.
) Let k and t be integers such that k Ou 0, t > 0, and 2 - t.
Then 8.
Oe k Oe 3, if k > 0.
sdim(Pe (V8.
)) = 8.
Oe 4, if k = 0.
Perfect enhanced power graphs It was proved in .
that every power graph of a group is perfect.
However, there exists a finite nilpotent group whose enhanced power graph is not perfect.
For example, let G = ha1 i y ha2 i y hb1 i y hb2 i y hc1 i y hc2 i, where o.
1 ) = o.
2 ) = 2, o.
1 ) = o.
2 ) = 3, and o.
1 ) = o.
2 ) = 5.
Then the elements a1 b1 , b1 c2 , a2 , b2 , and a1 c1 form a pentagon as an induced subgraph of Pe (G).
It follows that Pe (G) is not perfect, since a pentagon is not perfect.
ZahirovicA et al.
gave a characterization of finite nilpotent groups with perfect enhanced power graphs.
Theorem 4.
Theorem 6.
) A finite nilpotent group has perfect enhanced power graph if and only if this nilpotent group has at most two noncyclic Sylow subgroups.
A survey on enhanced power graphs of finite groups Xuanlong Ma et al.
On the other hand, the following theorem implies that there are many groups which do not have perfect enhanced power graphs, but whose clique number and chromatic number are equal.
Theorem 4.
Theorem 6.
) If a finite group G has an element with order equal to the exponent of G, then Pe (G) is weakly perfect.
Theorem 4.
Corollary 6.
) If G is a finite nilpotent group, then Pe (G) is weakly perfect.
Theorem 4.
Theorem 4.
) Let G be a finite group, and let p1 , p2 , .
, pn be all prime divisors of |G| for some n Ou 2.
If, for each i > 2.
G has the unique Sylow pi -subgroup, which is cyclic, then G has perfect enhanced power graph.
The above result implies the following theorem.
Theorem 4.
Corollary 4.
) Let G be a finite group of order pn q m , for some n, m Ou 0 and some primes p and q.
Then G has perfect enhanced power graph.
The following example shows that the sufficient condition of Theorem 4.
4 is not necessary.
Theorem 4.
Example 4.
) No Sylow subgroup of the alternating group A5 is unique, and the enhanced power graph of A5 is perfect.
The condition of Theorem 4.
4 cannot be weakened by removing the requirement for the Sylow subgroups to be cyclic, nor by removing the demand for the Sylow subgroups to be unique.
For example, the group Z30 y Z30 is abelian, and its Sylow subgroups are unique.
However.
Pe (Z30 y Z30 ) is not a perfect graph .
Theorem 4.
Proposition 4.
) The symmetric group Sn has a perfect enhanced power graph if and only if n O 7, and the alternating group An has perfect enhanced power graph if and only if n O 8.
Theorem 4.
Theorems 3.
31, 3.
33 and 3.
) The enhanced power graphs of U6n .
D2n and SD8n are perfect.
Theorem 4.
Theorems 3.
16 and 3.
) The enhanced power graphs of V8n and Q4n are Forbidden subgraphs in the enhanced power graph This section contains the results on the forbidden subgraphs of enhanced power graphs.
Chordal graphs, threshold graphs, cographs and split graphs form important classes that can be defined in terms of forbidden induced subgraphs.
A graph is said to be chordal if it contains no induced cycles of length greater than 3.
In other words, a chordal graph is a graph in which every cycle of length at least 4 has a chord.
This means that if a chordal graph has an induced cycle C, then C is isomorphic to C3 .
A graph is called a threshold graph if it has no induced subgraph isomorphic to the path P4 , the complete graph K4 , or 2K2 .
Chordal graphs and threshold graphs were considered, for example, in .
graph is called a cograph if this graph has no induced subgraph isomorphic to the path P4 .
A graph is said to be split if its vertex set is the disjoint union of two subsets A and B such that A induces a complete graph and B induces an empty graph.
A survey on enhanced power graphs of finite groups Xuanlong Ma et al.
Theorem 5.
Theorems 3.
) The following are equivalent for a finite group G:
Pe (G) is split.
Pe (G) is 2K2 -free.
G is a cyclic group, a dihedral group, or an elementary abelian 2-group.
Theorem 5.
Theorems 3.
) Pe (G) is threshold if and only if G is isomorphic to one of the following groups:
Z2 .
Z3 .
D6 .
Zn2 , where n is a positive integer at least 2.
Theorem 5.
Theorems 4.
) The following are equivalent for a nilpotent group G:
(I) Pe (G) is a chordal graph.
(II) Pe (G) is a cograph.
G has at most one noncyclic Sylow subgroup.
(IV) G O
= P y Zn , where P is a Sylow p-subgroup of G and (|P |, .
= 1.
A group is called a P -group if every nonidentity element of the group has prime order.
For example.
D2q is a P -group for some odd prime q.
A group is called a CP-group if every nontrivial element of the group has prime power order.
For example, any p-group is a CP -group, and D2qn is a CP -group for some odd prime q and positive integer n.
Clearly, a P -group is also a CP group.
The prime graph of a finite group G is a simple graph whose vertex set consists of all prime divisors of |G|, and two distinct vertices p and q are adjacent if there exists an element of order pq in G.
The prime graph of a group was first introduced by Gruenberg and Kegel in an unpublished manuscript studying integral representations of groups in 1975.
Theorem 5.
Propositions 4.
6, 4.
8 and 4.
) Let G be a group.
Pe (G) is a chordal graph as well as a cograph if one of the following holds:
G is a p-group.
Given a positive integer k, if |M O N | = k for any two distinct M.
N OO MG .
G is a dihedral group.
G is a generalized quaternion group.
G is a CP -group.
G is a group with null prime graph.
G is isomorphic to one of the P SL.
, .
= 4, 7, 8, 9, .
P SL.
, .
Sz.
, and Sz.
Theorem 5.
Propositions 4.
14, 4.
15, 4.
17, and 4.
) The following hold:
Pe (Sn ) is a cograph if and only if Pe (Sn ) is a chordal graph, if and only if n O 5.
Pe (An ) is a cograph if and only if n O 6.
Pe (An ) is a chordal graph if and only if n O 7.
Theorem 5.
Corollary 4.
) Let G be a group, and let H be a subgroup of G such that G = H y Zn , where (|H|, .
= 1.
Then Pe (G) is a cograph .
a chordal grap.
if and only if Pe (H) is a cograph .
a chordal grap.
A survey on enhanced power graphs of finite groups Xuanlong Ma et al.
Theorem 5.
Lemma 4.
) Let G be a group and let p, q be two distinct primes.
Then Pe (G) is a chordal graph as well as a cograph if one of the following holds:
Ae (G) = .
, p, q, p.
and G has a unique subgroup of order p or q.
Ae (G) = .
, p, q, p.
and either G has a unique cyclic subgroup of order pq, or the intersection of all cyclic subgroups of order pq has size p or q.
Ae (G) = .
, p, q, pq, p2 } and either G has a unique cyclic subgroup of order pq, or the intersection of all cyclic subgroups of order pq is hai where a OO K(G) and o.
OO .
, .
Theorem 5.
Theorem 4.
) Let G be a group of order at most 24.
Then Pe (G) is a cograph if and only if G is isomorphic to neither Z2 y Q12 nor the semidirect product of Z3 and D8 with action kernel Z2 y Z2 .
Theorem 5.
Theorem 4.
) If G is a minimum order group such that Pe (G) is not a chordal graph, then |G| = 36.
In particular.
Pe (Z6 y Z6 ) is not chordal.
Enhanced power graph and other graphs In this section, we collect some results on the relationships between enhanced power graph and other graphs.
Theorem 6.
Theorem .
) Let G and H be two groups.
If the power graphs of G and H are isomorphic, then their enhanced power graphs are also isomorphic.
Theorem 6.
Theorem .
) For a group G, the following conditions are equivalent:
the power graph of G is equal to the enhanced power graph of G.
every cyclic subgroup of G has prime power order.
the prime graph of G is a null graph.
It was showed in .
that a group G with these properties is one of the following: a p-group.
Frobenius group whose kernel is a p-group and complement a q-group.
a 2-Frobenius group where F1 and G/F2 are p-groups and F2 /F1 is a q-group.
or G has a normal 2-subgroup with quotient group H, where S O H O Aut(S) and S O = A5 or A6 .
All these types of group exist.
Clearly, if the vertices x and y are joined in the power graph of G, then they are joined in the commuting graph.
Therefore, the power graph is a spanning subgraph of the commuting graph.
Theorem 6.
Theorem .
) For a finite group G, the following are equivalent:
the enhanced power graph of G is equal to its commuting graph.
G has no subgroup Zp y Zp for some prime p.
the Sylow subgroups of G are cyclic or .
or p = .
generalized quaternion.
It was showed in .
that a group satisfying these conditions is either a cyclic p-group for some prime p, or satisfies the following: if O(G) denotes the largest normal subgroup of G of odd order, then O(G) is metacyclic.
H = G/O(G) is a group with a unique involution, say z, and H/hzi is a cyclic or dihedral 2-group, a subgroup of PeL.
, .
containing PSL.
, .
for q an odd prime power, or A7 .
An example for the second case is the direct product of the Frobenius group of order 253 and SL.
, .
A survey on enhanced power graphs of finite groups Xuanlong Ma et al.
Ie Oe Theorem 6.
Theorem 3.
) Let G and H be two groups.
If Pe (G) O = Pe (H), then P (G) O Ie Oe P (H).
Theorem 6.
Corollary 3.
) For all groups G and H, the following are equivalent:
Power graphs of G and H are isomorphic.
Directed power graphs of G and H are isomorphic.
Enhanced power graphs of G and H are isomorphic.
Theorem 6.
Corollary 4.
) Let G be a group.
Then Ie Oe Aut(G) OI Aut( P (G)) OI Aut(P(G)) OI Aut(Pe (G)).
Theorem 6.
Theorem 4.
) Let G and H be two groups.
Then any isomorphism from P(G) to P(H) is an isomorphism from Pe (G) to Pe (H).
The deep commuting graph of a group G is the graph DC(G) whose vertex set is G, two distinct vertices are adjacent if and only if their pre-images in every central extension of G .
hat is, every group H with a central subgroup Z such that H/Z O = G) commute.
Note that E(DC(G)) is contained in the set of edges of the commuting graph of G and contains the set of edges of the enhanced power graph of G.
Theorem 6.
Theorem 4.
) Let G be a group.
DC(G) = Pe (G) if and only if G has the following property: Let H be a Schur cover of G, with H/Z = G.
Then for any subgroup A of G, with B the corresponding subgroup of H .
o Z O B and B/Z = A), if B is abelian, then A is Let P O (G) be the graph obtained by deleting only the identity element of G in P(G) and this is called deleted power graph of G.
Similarly.
PeO (G) denotes the graph obtained by deleting only the identity element of G in Pe (G) and this is called deleted enhanced power graph of G.
Theorem 6.
Theorem 2.
) For any group G.
P O (G) is connected if and only if the PeO (G) is connected.
Miscellaneous properties of the enhanced power graph In this section, we present some miscellaneous properties of the enhanced power graph of a group, including vertex connectivity, diameter, automorphism group, independence number.
Eulerian, matching number and so on.
Theorem 7.
Theorem 1.
) Let G be a finite p-group such that G is neither cyclic nor generalized quaternion group.
Then (Pe (G)) = 1.
Theorem 7.
Theorem 1.
) Let G be a finite noncyclic abelian group.
Then (Pe (G)) = 1 if and only if G is a p-group.
Theorem 7.
Theorem 1.
) Let G be a noncyclic abelian non-p-group such that G O = G1 y Zn , gcd(|G1 |, .
= 1 and G1 is a p-group with no cyclic Sylow subgroup.
Then (Pe (G)) = n.
A survey on enhanced power graphs of finite groups Xuanlong Ma et al.
Theorem 7.
Theorems 4.
1, 4.
2, 4.
5, and 4.
) For n Ou 3, (Pe (D2n )) = 1, (Pe (Q2n )) = 2, and (Pe (Sn )) = 1 if and only if either n or n Oe 1 is prime.
For n Ou 7, (Pe (An )) = 1 if and only if one of n, n Oe 1, n Oe 2, n/2, .
Oe .
/2, .
Oe .
/2 is prime.
Recently.
Costanzo et al.
studied the deleted enhanced power graph of a direct product.
Theorem 7.
Theorem A]) If G and H are nontrivial groups such that PeO (G y H) is connected, then diam(PeO (G y H)) O 7.
Theorem 7.
Theorem B]) If G and H are groups such that PeO (G y H) is connected with diam(PeO (G y H)) O 2, then (PeO (G)) and (PeO (H)) are connected, and diam(PeO (G)) O 2 or diam(PeO (H)) O 2.
Recall that a Z-group is a group where every Sylow subgroup is cyclic.
Recently.
Costanzo et .
investigated PeO (G) for a Z-group G.
Theorem 7.
Theorem A]) Let G be a Z-group.
Then PeO (G) is disconnected if and only if G is a Frobenius group.
Theorem 7.
Theorem B]) If G is a Z-group and PeO (G) is connected, then diam(PeO (G)) O Theorem 7.
Theorem C]) If G is a Z-group, then diam(PeO (G)) O 2 if and only if Z(G) 6= .
For a positive integer n, let A.
denote the set of prime divisors of n.
Theorem 7.
Theorem D]) Let G be a group, g OO G, and A = A.
Write pOOA where each gp is a p-element for p OO A and gp gq = gq gp for all p, q OO A.
Then g is a dominating vertex for PeO (G) if and only if, for each p OO A, a Sylow p-subgroup P of G is cyclic or generalized quaternion and hgp i O P O Z(G).
The above result offered a generalization of Theorem 3.
2 in .
ee Theorem 2.
That is, for a nilpotent group G, the graph PeO (G) is dominatable if and only if G has a cyclic or generalized quaternion Sylow subgroup.
Theorem 7.
Corollary .
) Let G be a finite group.
Then O(Pe (G)) = max.
: g OO G}.
Theorem 7.
Theorem 2.
) The enhanced power graph of a group G is complete if and only if G is cyclic.
Theorem 7.
Theorem 2.
) Let G be a group of order n.
Then Pe (G) is Eulerian if and only if n is odd.
A survey on enhanced power graphs of finite groups Xuanlong Ma et al.
In .
, the authors defined graph Sp .
, where p is a prime and a is a tuple consisting of some positive integers.
Theorem 7.
Theorem 5.
) A graph e is the enhanced power graph of a finite abelian group if and only if eO = ni=1 Spi .
i ) for some tuples ai of positive integers and for some pairwise different primes p1 , p2 , .
, pn .
Theorem 7.
Theorem 4.
) Z2 is the unique nontrivial finite group whose enhanced power graph has an abelian automorphism group.
Theorem 7.
Theorem 4.
) Z2 .
Z3 , and the Klein group are the only nontrivial finite groups whose automorphism groups of their enhanced power graphs have square free orders.
Theorem 7.
Theorem 4.
) Z2 and Z2 y Z4 are the only nontrivial finite groups whose automorphism groups of their enhanced power graphs have prime power orders Theorem 7.
Theorem 3.
) For any finite group G, the minimum degree of Pe (G) is mOe1, where m is the order of the smallest maximal cyclic subgroup of G.
For a group G, a subset M (G) := .
1 , x2 , .
, xm } of G is called an essential cyclic set if the following hold:
For any g OO G, there exists xi OO M (G) such that hgi = hxi i.
hxi i = 6 hxj i for distinct indices i, j.
For every i, hxi i is a maximal cyclic subgroup of G.
Denote by i(G) the subset .
OO M (G) : hxi O hyi = .
for any y OO M (G) \ .
} of M (G).
Theorem 7.
Theorem 3.
) Suppose that G is a group with .
(G)| = 0.
Then the rainbow connection number 1, if G is cyclic.
2, if G has an awning and is noncyclic.
rc(Pe (G)) = 3, if G has no awnings.
where the definition of an awning can be found in .
Definition 2.
An independent set of e is a set of vertices none of two are adjacent in e.
The independence number of e, denoted by .
, is the largest cardinality of an independent set of e.
Theorem 7.
Theorem 3.
) For any finite group G, the independence number of Pe (G) is equal to the number of maximal cyclic subgroups of G.
Furthermore, if G is nilpotent and the prime factors of |G| are p1 , p2 , .
, pr , then (Pe (G)) = m1 m2 A A A mr , where mi is the number of maximal cyclic subgroups of a Sylow pi -subgroup.
A survey on enhanced power graphs of finite groups Xuanlong Ma et al.
A matching of e is a set of edges such that no two of them are incident to the same vertex.
The matching number of e, denoted by .
, is the maximum cardinality of a matching.
Theorem 7.
Theorem 3.
) For any finite group G.
If G has odd order, then (Pe (G)) = (|G| Oe .
/2.
If G has even order, then |G| Oe t 1
|G|
O (Pe (G)) O where t is the number of all involutions of G.
Theorem 7.
Theorem 3.
) For any finite p-group G, |G|Oe1 p > 2.
(Pe (G)) = |G|Oet 1 , p = 2.
where t is the number of all involutions of G.
A group G is a 2-Frobenius group if this group has two normal subgroups K and L such that L is a Frobenius group with Frobenius kernel K and G/K is a Frobenius group with Frobenius kernel L/K.
The best known example of a 2-Frobenius group is the symmetric group S4 of order Theorem 7.
Theorem A]) Let G be a 2-Frobenius group with K as in the definition.
|K| is divisible by at least two distinct primes, then PeO (G) has |K| 1 connected components.
Let mp (G) denote the number of subgroups of order p of a group G.
Theorem 7.
Theorem B]) Let G be a 2-Frobenius group, and assume that K and G/L are p-groups for some prime p, where K and L are as in the definition and K has prime power Then PeO (G) has |K| mp (G) connected components.
Denote by mOp (G) the number of subgroups of order p in G that are not centralized by an element of prime order other than p.
Theorem 7.
Theorem C]) Let G be a 2-Frobenius group, and let p be a prime.
Assume that K is a p-group for some prime p and that G/L is not a p-group, where K and L are as in the Then PeO (G) has |K| |L/K| mOp (G) connected components.
Open questions and other work This section presents open problems on enhanced power graphs of groups.
Note that the enhanced power graph of a group is a union of complete subgraphs on the maximal cyclic subgroups of this group.
Cameron .
put forward the following question.
Problem 1.
Question .
) Is there a simple algorithm for constructing the directed power graph or the enhanced power graph from the power graph, or the directed power graph from the enhanced power graph? A survey on enhanced power graphs of finite groups Xuanlong Ma et al.
The deep commuting graph of a group was defined by Cameron and Kuzma .
Problem 2.
Question .
) What can be said about groups G for which DC(G) = Pe (G)? Problem 3.
Open proble.
) Characterize all finite non-abelian groups G such that Pe (G) is In fact.
Theorems 2.
4 and 2.
7 are two solutions to Problem 3.
Maybe, by other methods, one can characterize all finite groups G such that Pe (G) is dominatable.
It is clear that O(P(G)) O O(Pe (G)).
It was proved in .
Theorem 4.
that there exists a function f on the natural numbers such that, for any finite group G.
O(Pe (G)) O f (O(P(G))).
For example, let f (O(P(G))) be the least common multiple of .
, 2, .
O(P(G))}.
Problem 4.
Question .
) Find the best possible function f in .
An upper bound for the chromatic number of the enhanced power graph is given in .
Theorem .
Theorem 4.
For a finite group G, let S be the set of orders of elements of G, i.
, .
N(Pe (G)) O nOOS where i is EulerAos function.
Note that the bound of .
holds for abelian groups.
In fact, if G is an abelian group, then S is the set of divisors of the exponent of G, and so the sum on the right of .
is the exponent of G, which is the largest element order in G.
Problem 5.
Question .
) Find a formula for the chromatic number of the enhanced power graph of a finite group.
If a finite graph e is isomorphic to an induced subgraph of the enhanced power graph of some finite group G, then we say that e is embeddable in the enhanced power graph of G.
Problem 6.
Question .
) .
What is the smallest group for which a given graph is embeddable in the enhanced power graph of the group? .
What is the smallest group in which every graph on n vertices can be embedded the enhanced power graph of the group? Problem 7.
Question .
) For which finite groups is the enhanced power graph a perfect graph, or a cograph, or a chordal graph, or a split graph, or a threshold graph? BosUnjak et al.
and ZahirovicA et al.
studied perfect enhanced power graphs of groups.
Ma.
Lv, and She .
classified finite groups whose enhanced power graphs are split graphs and threshold graphs.
They also classified finite nilpotent groups whose enhanced power graphs are chordal graphs and cographs, and gave some families of non-nilpotent groups whose enhanced power graphs are chordal graphs and cographs.
These results provide a partial solution to Problem 7.
A survey on enhanced power graphs of finite groups Xuanlong Ma et al.
Problem 8.
Question .
) Is it true that the complement of the enhanced power graph has just one connected component, apart from isolated vertices? Two vertices u, v of a graph e are open twins if they have the same open neighbourhoods.
are closed twins if they have the same closed neighbourhoods.
If x and y are twins .
pen or closed twin.
, then we may collapse them to a single vertex.
this process is called twin reduction.
Clear, the automorphism group Aut.
of a graph e preserves twin relations on e, and that vertices in a twin equivalence class can be permuted arbitrarily.
It follows by induction that the group induces an automorphism group on the cokernel eO of e, say AutOe .
O ).
The twin reduction on e is faithful if AutOe .
O ) = Aut.
O ).
Problem 9.
Question .
) Let G be a group.
When is twin reduction on Pe (G) faithful? .
What is the automorphism group of the cokernel of Pe (G)? Problem 10.
Question .
) For which non-abelian finite simple group G is it the case that the twin reduction on the enhanced power graph of G is faithful? Problem 11.
Question .
) For which finite groups is the power graph equal to the enhanced power graph? Problem 12.
Question .
) For which .
groups is the enhanced power graph equal to the commuting graph? In .
, the authors solved Problems 11 and 12 for the special case of finite groups .
Theorems 28 and 30, respectivel.
Problem 13.
Question .
) What can be said about the difference of the enhanced power graph and the power graph, or the difference of the commuting graph and the enhanced power graph? In particular, for which groups is either of these graphs connected? The multiset dimension was introduced by Rinovia Simanjuntak et al.
as a variation of metric dimension.
It was considered in .
, .
Here we suggest the following open problem.
Problem 14.
For any finite group G, describe the multiset dimension of the enhanced power graph of G.
The locating chromatic number of a graph was introduced by Chartrand et al.
It is equal to the minimum number of colours needed in a locating colouring of the graph.
Let us refer to .
for more information on the locating-chromatic number.
We propose the following open problem.
Problem 15.
For any finite group G, describe the locating-chromatic number of the enhanced power graph of G.
The investigation of graph labelings forms a large and important research direction.
Many valuable classes of graph labelings have been investigated in the literature, including cordial labelings .
, distance labelings .
, face-antimagic labelings .
, graceful labelings .
, integer additive labelings .
, irregular total labelings .
, supermagic labelings .
and vertex irregular reflexive labelings .
, .
The following general problem is an interesting suggestion for future A survey on enhanced power graphs of finite groups Xuanlong Ma et al.
Problem 16.
Investigate enhanced power graphs with labelings of various essential classes.
For any finite group G, describe -labelings, cordial labelings, distance labelings, face-antimagic labelings, graceful labelings, integer additive set-labelings, irregular total labelings, magic and antimagic graph labelings, super antimagic labelings, supermagic labelings, and vertex irregular reflexive labelings of the enhanced power graph of G.
In conclusion, we mention a few pertinent references which complement the results presented above and can also be used in the future work.
The proper enhanced power graph of a group G is the induced subgraph of the enhanced power graph on the set G \ D, where D is the set of dominating vertices of the enhanced power graph of G.
Bera and Dey .
classified all nilpotent groups such that their proper enhanced power graphs are connected and determined their diameters.
They also explicitly found the domination number of the proper enhanced power graph of a finite nilpotent group.
The enhanced power graph or cyclic graph of a semigroup S is a simple graph whose vertex set is S and two vertices x, y OO S are adjacent if and only if x, y OO hzi for some z OO S, where hzi is the subsemigroup of S generated by z.
In .
, 35, 36, .
, several graph theoretical properties of the enhanced power graph of semigroups were studied, including the dominating number, independence number, genus, connectedness, minimum degree, chromatic number and so on.
Moreover, the authors characterized the semigroups S such that the enhanced power graph of S is complete, bipartite, regular, is a tree, or is a null graph.
Moreover, the structure of the enhanced power graph of any semigroup was described.
Dupont et al.
introduced the enhanced quotient graph of the quotient of a finite group, and gave necessary and sufficient conditions for the graph to be complete and Eulerian.
Acknowledgement The authors are grateful to two anonymous reviewers for careful reports.
The first author Xuanlong Ma was supported by the National Natural Science Foundation of China (Grant Nos.
, the Natural Science Basic Research Program of Shaanxi (Program No.
2020JQ.
, and the Young Talent fund of University Association for Science and Technology in Shaanxi.
China (Program No.
The fourth author Kaishun Wang was supported by the National Key R&D Program of China .
0YFA0712.
and NNSF of China .
71039, 12131.
References