# Forbidden subgraphs in enhanced power graphs of finite groups

Xuanlong Ma1, Samir Zahirović2,111Corresponding author , Yubo Lv3, and Yanhong
She1
1School of Science, Xi’an Shiyou University, Xi’an, 710065, China
2Department of Mathematics and Informatics, Faculty of Sciences,
University of Novi Sad, Dositej Obradović Square 3, Novi Sad, 21000, Serbia
3School of Mathematical Sciences,
Guizhou Normal University, Guiyang, 550001, China

###### Abstract

The enhanced power graph of a group is the simple graph whose vertex set is
consisted of all elements of the group, and whose any pair of vertices are
adjacent if they generate a cyclic subgroup. In this paper, we classify all
finite groups whose enhanced power graphs are split and threshold. We also
classify all finite nilpotent groups whose enhanced power graphs are chordal
graphs and cographs. Finally, we give some families of non-nilpotent groups
whose enhanced power graphs are chordal graphs and cographs. These results
partly answer a question posed by Peter J. Cameron.

Key words: Enhanced power graph; Split graph; Cograph; Chordal graph;
Threshold graph; Nilpotent group

2020 MSC: 05C25; 05C38

††E-mail addresses<EMAIL_ADDRESS>(X. Ma),
<EMAIL_ADDRESS>
(S. Zahirović<EMAIL_ADDRESS>(Y. Lv<EMAIL_ADDRESS>(Y. She)

##  1 Introduction

The undirected power graph $\mathcal{P}(G)$ of a group $G$ has vertex set $G$,
and two distinct elements of $G$ are adjacent in the undirected power graph if
one is a power of the other. The concept of the directed power graph was first
introduced by Kelarev and Quinn [25], and the undirected power graph was first
studied by Chakrabarty et al. [13]. In recent years, the interest among
researchers in the undirected power graph has been growing; see, for example,
[8, 10, 11, 20, 28, 32]. Also, see [2, 9, 26] for a survey of results and open
problems on the undirected power graph.

Let $G$ be a finite group. The enhanced power graph of $G$, denoted by
$\mathcal{P}_{e}(G)$, is the simple graph whose vertex set is the set of all
elements of $G$, and two distinct vertices $x,y$ are adjacent if and only if
$\langle x,y\rangle$ is a cyclic subgroup of $G$. The term enhanced power
graph was introduced by Aalipour et al. [1]; in their paper, they studied the
enhanced power graph in order to measure how close the undirected power graph
is to the commuting graph. It is important to mention that this notion was
studied even earlier in [4, 29]. It is worth noting that in [4, 29], as well
as in some newer papers (e.g. [14, 15]), the authors used the term cyclic
graph instead. Furthermore, Abdolahi et al. [3] studied the noncyclic graph,
i.e. the complement of the enhanced power graph, even earlier.

Recently, the enhanced power graphs has received considerable attention.
Aalipour et al. [1] showed that every maximal clique of $\mathcal{P}_{e}(G)$
is a maximal locally cyclic subgroups of $G$. In 2020, Zahirović, Bošnjak, and
Madarász [36] showed that any isomorphism between undirected power graph of
finite groups is an isomorphism between enhanced power graphs of these groups.
Panda, Dalal, and Kumar [33] studied the minimum degree, independence number,
and matching number of enhanced power graphs of finite groups. In [27], the
authors obtained an explicit formula for the metric dimension of the enhanced
power graph of a finite group. Bera, Dey, and Mukherjee [6] completely
characterized all abelian groups such that their proper enhanced power graphs
are connected, where the proper enhanced power graph of $G$ is the graph
obtained by deleting the identity element from $\mathcal{P}_{e}(G)$. Dalal and
Kumar [16] studied the enhanced power graphs of some special groups. Further,
Cameron and Kuzma [12] defined a graph whose vertex set is a finite group $G$,
whose edge set is contained in that of the commuting graph of $G$ and contains
the enhanced power graph of $G$; they called it the deep commuting graph. In
[12], they obtained conditions for the deep commuting graph to be equal to
either of the enhanced power graph and the commuting graph.

A number of important graph classes, including cographs, chordal graphs, split
graphs, and threshold graphs, can be defined either structurally or in terms
of forbidden induced subgraphs. Forbidden subgraphs of undirected power graphs
of groups have been studied by Doostabadi et al. [19] and Cameron et al. [30].

In [9], Cameron described various graphs whose vertex set is the universe of a
group and whose edges reflect group structure in some way, and he proposed the
following question.

###### Question 1.1

([9, Question 14]) For which finite groups is the enhanced power graph a
perfect graph, a cograph, a chordal graph, a split graph, or a threshold
graph?

Recently, Bošnjak, Madarász, and Zahirović [7, 36] studied perfectness of the
enhanced power graph of a group. Motivated by Question 1.1, in this paper, we
study forbidden subgraphs of enhanced power graphs of finite groups. This way,
we classify all finite groups whose enhanced power graphs are split graphs and
threshold graphs. We also classify all finite nilpotent groups whose enhanced
power graphs are chordal graphs and cographs. Finally, we give some families
of non-nilpotent groups whose enhanced power graphs are chordal graphs and
cographs. Our results partly answer Question 1.1.

##  2 Preliminaries

In this section, we briefly recall some notation, terminology, and basic
results which we need in the remainder of this paper.

All groups considered in this paper are finite. We denote groups by capital
letters, usually $G$, and its identity element is usually denoted by $e$. The
order of a group element $g$ is denoted by $o(g)$, the set of orders of
elements of a group $G$ is denoted by $\pi_{e}(G)$. An element of order $2$ is
called an involution. By $\mathcal{M}_{G}$, we denote the set of all maximal
cyclic subgroups of $G$. Notice that $|\mathcal{M}_{G}|=1$ if and only if $G$
is cyclic. The cyclic group of order $n$ is denoted by $\mathbb{Z}_{n}$. For a
prime number $p$, a finite elementary $p$-group is an abelian group of
exponent $p$, and it is isomorphic to $\mathbb{Z}_{p}^{n}$ for some
$n\in\mathbb{N}$.

We remind the reader that a finite nilpotent group is the direct product of
its Sylow subgroups. Also, it is well known that both $p$-groups and abelian
groups are nilpotent.

By $D_{2n}$, we denote the dihedral group of order $2n$. Let us recall that
$D_{2n}$ consists of $n$ reflection, $n-1$ rotations, and the identity
mapping. Together with the identity mapping, all rotations make up a cyclic
subgroup of order $n$, and each reflection makes up a maximal cyclic subgroup
of order $2$ of $D_{2n}$. Dihedral group $D_{2n}$ has presentation

$D_{2n}=\langle a,b:a^{n}=b^{2}=e,bab=a^{-1}\rangle.$ (1)

Notice that, for $a$ and $b$ from the above presentation, $\langle a\rangle$
is the cyclic subgroup containing all rotations, and $a^{i}b$ is a reflection
for every $i$. Therefore,

$\mathcal{M}_{D_{2n}}=\\{\langle a\rangle,\langle b\rangle,\langle
ab\rangle,\langle a^{2}b\rangle,\ldots,\langle a^{n-1}b\rangle\\}.$ (2)

The generalized quaternion group $Q_{4m}$ of order $4m$, $m\geq 2$, is the
group defined by presentation

$Q_{4m}=\langle x,y:x^{m}=y^{2},x^{2m}=e,y^{-1}xy=x^{-1}\rangle.$ (3)

Let us remark that, for $x$, $y$ and $m$ from the above presentation, $x^{m}$
is the unique element of $Q_{4m}$ of order $2$. Also, $\langle x\rangle$ is
its maximal cyclic subgroup of order $2m$, and $\langle x^{i}y\rangle$ is a
maximal cyclic subgroup of order $4$ for each $i$, $0\leq i<m$. Therefore,

$\mathcal{M}_{Q_{4m}}=\\{\langle x\rangle,\langle xy\rangle,\langle
x^{2}y\rangle,\ldots,\langle x^{m}y\rangle\\}.$ (4)

All graphs considered in this paper are finite, undirected, and with no loops
and no multiple edges. Let $\Gamma$ be a graph. The vertex set of $\Gamma$ is
denoted by $V(\Gamma)$, and the edge set by $E(\Gamma)$. A graph is
$\Gamma$-free if it has no induced subgraph isomorphic to $\Gamma$. A graph is
a star if it is a tree with $n$ vertices in which one vertex has degree $n-1$
and every other vertex has degree $1$. We denote by $P_{n}$, $C_{n}$, and
$K_{n}$ the path with $n$ vertices, the cycle of length $n$, and the complete
graph of order $n$, respectively. Note that the length of a path with $n$
vertices is $n-1$. Also, we use $2K_{2}$ to denote the disjoint union of two
copies of $K_{2}$. If two distinct vertices $x$ and $y$ of $\Gamma$ are
adjacent, then we denote this by $x\sim_{\Gamma}y$, or shortly by $x\sim y$.
In particular, a path with $n$ vertices is usually denoted by $x_{1}\sim
x_{2}\sim\cdots\sim x_{n}$, and a cycle of length $n$ is denoted by $x_{1}\sim
x_{2}\sim\cdots\sim x_{n}\sim x_{1}$, where $x_{i}\in V(\Gamma)$.

By $x\stackrel{{\scriptstyle e}}{{\sim}}y$, we denote that the elements $x$
and $y$ of a group are adjacent in the enhanced power graph. The closed
neighborhood of a vertex $x$ in a graph $\Gamma$ is the set
$\\{x\\}\cup\\{v\in V(\Gamma):v\sim_{\Gamma}x\\}$. If elements $x$ and $y$ of
a group $G$ have the same closed neighborhood in $\mathcal{P}_{e}(G)$, we
write $x\stackrel{{\scriptstyle e}}{{\equiv}}y$; in that case, we also say
that $x$ and $y$ are closed twins in $\mathcal{P}_{e}(G)$.

In this paper, we study several properties of the enhanced power graph of a
group which are characterizable using “forbidden subgraphs”. We introduce now
their definitions, as well as their characterizations by forbidden subgraphs.
A split graph is a graph whose 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. It is known that a graph is split if and only if it does not contain
$C_{4}$, $C_{5}$, nor $2K_{2}$ as an induced subgraph. A graph is called a
threshold graph if it can be constructed by addition of an isolated vertex and
addition of a dominating vertex, i.e. a vertex adjacent to all vertices.
Equivalently, a graph is threshold if and only if it has no induced subgraph
isomorphic to $P_{4}$, $C_{4}$, or $2K_{2}$. A graph is called 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, i.e. an edge incident to a pair of nonconsecutive vertices of the
cycle. Notice that, if a graph is $C_{4}$-free and $P_{4}$-free, then it is
chordal. Note, however, that this sufficient condition is not a necessary one
as well. A graph is called a cograph if it can be constructed from isolated
vertices by disjoint union and complementation. It is known that a graph is a
cograph if and only if it is $P_{4}$-free.

The relations between the above-introduced families of graphs is presented by
Diagram 1; it is well known that cographs and split, threshold, and chordal
graphs are all perfect graphs. Note that perfectness of a graph is also a
property which, by the Strong Perfect Graph Theorem, is characterizable by
forbidden subgraphs.

threshold graphscographsperfect graphssplit graphschordal graphs Diagram 1:

Notice that the cyclic subgroup generated by a pair of elements $x$ and $y$ of
a group $G$ is included in every subgroup of $G$ containing $x$ and $y$.
Therefore, it is clear that, for any subgroup $H$ of $G$, $\mathcal{P}_{e}(H)$
is an induced subgraph of $\mathcal{P}_{e}(G)$. The proof of the following
result is straightforward.

###### Lemma 2.1

Let $G$ be a group and $H$ its subgroup. If $\mathcal{P}_{e}(G)$ is split,
threshold, chordal, chordal, or a cograph, then $\mathcal{P}_{e}(H)$ is also
split, threshold, chordal, chordal, or a cograph, respectively.

We introduce now the following important lemma proven by Aalipour et al.[1].

###### Lemma 2.2

([1, Lemma 33]) Let $G$ be a finite group, and let $C$ be a maximal clique of
$\mathcal{P}_{e}(G)$. Then $C$ is a maximal cyclic subgroup of $G$.

##  3 Split graphs and threshold graphs

In this section, we classify all groups whose enhanced power graphs are split
and threshold graphs. Before proving Theorem 3.3, we shall prove the following
two lemmas, which are required for their proofs.

###### Lemma 3.1

Let $G$ be a group with $2K_{2}$-free enhanced power graph. Then $G$ has at
most one maximal cyclic subgroup of order greater than $2$.

Proof. If $G$ is a cyclic group or has exponent $2$, then the assertion of the
lemma obviously holds. So suppose further that $G$ is a noncyclic group.

Suppose, for contradiction, that $G$ has two distinct maximal cyclic
subgroups, say $\langle x\rangle$ and $\langle y\rangle$, of orders greater
than $2$. Since $\langle x\rangle,\langle y\rangle<\langle x,y\rangle$, and
since $\langle x\rangle$ and $\langle y\rangle$ are maximal cyclic subgroups,
the group $\langle x,y\rangle$ is not cyclic. Thus, we get
$x\not\stackrel{{\scriptstyle e}}{{\sim}}y$, $x\not\stackrel{{\scriptstyle
e}}{{\sim}}y^{-1}$, $x^{-1}\not\stackrel{{\scriptstyle e}}{{\sim}}y$, and
$x^{-1}\not\stackrel{{\scriptstyle e}}{{\sim}}y^{-1}$. Therefore, the subgraph
of $\mathcal{P}_{e}(G)$ induced by $\\{x,x^{-1},y,y^{-1}\\}$ is isomorphic to
$2K_{2}$, which is in contradiction with the assumption that
$\mathcal{P}_{e}(G)$ is $2K_{2}$-free. This proves the lemma.
$\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

###### Lemma 3.2

Let $G$ be a group. Then $\mathcal{P}_{e}(G)$ is $2K_{2}$-free if and only if
$G$ is a cyclic group, a dihedral group, or an elementary abelian $2$-group.

Proof. Since $\mathcal{P}_{e}(\mathbb{Z}_{2}^{n})$ is a star for every $n\geq
2$, $\mathcal{P}_{e}(\mathbb{Z}_{2}^{n})$ is $2K_{2}$-free. Also, since the
enhanced power graph of a cyclic group is complete, it is $2K_{2}$-free too.
Now, it only remains to show that $\mathcal{P}_{e}(D_{2n})$ is also
$2K_{2}$-free. Suppose that some four-element set $D$ induces a subgraph of
$\mathcal{P}_{e}(D_{2n})$ isomorphic to $2K_{2}$. Notice that $e\not\in D$
since $e$ is adjacent to all elements of the group. Furthermore, $D$ contains
no reflection, since every reflection is adjacent to no nonidentity element.
Therefore, $D$ contains only rotations, but that implies that $D$ induces a
complete subgraph of $\mathcal{P}_{e}(D_{2n})$, which is a contradiction. This
proves one implication of the lemma.

Suppose now that $\mathcal{P}_{e}(G)$ is $2K_{2}$-free. It suffices to prove
that if $G$ is noncyclic, then $G$ is either a dihedral group or an elementary
abelian $2$-group. Now, let us assume that $G$ is not cyclic. If every element
of $G$ is an involution, then $G$ is an elementary abelian $2$-group, as
desired. Therefore, we may assume that $G$ has an element of order greater
than $2$. Then by Lemma 3.1, $G$ has a unique maximal cyclic subgroup $\langle
a\rangle$ of order is at least $3$. Note that $\langle a\rangle$ contains all
elements of $G$ of order greater than $2$. Now, let $b\in G\setminus\langle
a\rangle$. Then $ab\notin\langle a\rangle$. It follow that $o(b)=o(ab)=2$
since $ab\not\in\langle a\rangle$, and so

$bab=b(ab)=bb^{-1}a^{-1}=a^{-1}.$ (5)

We deduce that $G$ is nonabelian. Moreover, (5) also implies that $\langle
a\rangle\unlhd G$, and hence $\langle a\rangle\langle b\rangle$ is a subgroup
of $G$.

In order to prove that $\langle a\rangle\langle b\rangle=G$, suppose that
$g\in G\setminus\langle a\rangle$, and let us prove that $g\in\langle
a\rangle\langle b\rangle$. It is sufficent to prove that $gb\in\langle
a\rangle$. Suppose, for contradiction, that $gb\notin\langle a\rangle$. Then
$o(g)=o(gb)=2$ and $gbg=gg^{-1}b^{-1}=b^{-1}$, which implies that $gb=bg$.
Similarly, we have that $xax=a^{-1}$ for every $x\in G\setminus\langle
a\rangle$. Also, since $gba\notin\langle a\rangle$, $gba$ is an involution. As
a result, we have

$a^{-1}=a^{-1}(gb)(gb)=\big{(}(gb)a\big{)}^{-1}(gb)=(gba)gb=g(bab)g=ga^{-1}g=a,$

which is a contradiction as $o(a)\geq 3$.

We conclude that $g\in\langle a\rangle\langle b\rangle$, which implies that
$G=\langle a\rangle\langle b\rangle=\langle a,b\rangle$. Thus, by (5) and the
presentation of the dihedral group, it follows that $G\cong D_{2n}$ where
$n=o(a)$. This proves the lemma. $\hfill\Box\vskip 6.0pt plus 2.0pt minus
2.0pt$

Now, we are ready to prove the main theorem of the section.

###### Theorem 3.3

The following are equivalent for a finite group $G$:

  1. (a)

$\mathcal{P}_{e}(G)$ is split;

  2. (b)

$\mathcal{P}_{e}(G)$ is threshold;

  3. (c)

$\mathcal{P}_{e}(G)$ is $2K_{2}$-free;

  4. (d)

$G$ is a cyclic group, a dihedral group, or an elementary abelian $2$-group.

Proof. It is easily seen that (d) implies (a) and (b). Since split graph and
threshold graph are $2K_{2}$-free, any of (a) and (b) implies (c). Finally, by
Lemma 3.2, (c) implies (d), which finishes the proof of the theorem.
$\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

##  4 Chordal graphs and cographs

In this section, we investigate which groups have chordal enhanced power
graph, and we study which groups have the enhanced power graph that is a
cograph. In the first subsection, we classify all finite nilpotent groups
whose enhanced power graph has the above mentioned properties, and in the
second one, we turn our focus on non-nilpotent finite groups.

In [36], it was proven that, if groups $G$ and $H$ have relatively prime
orders, then $P_{e}(G\times H)$ is the strong graph product of $P_{e}(G)$ and
$P_{e}(H)$; see [36, Lemma 2.1]. Consequently, for
$(g_{1},h_{1}),(g_{2},h_{2})\in G\times H$, $(g_{1},h_{1})\neq(g_{2},h_{2})$,
we have that $(g_{1},h_{1})\stackrel{{\scriptstyle e}}{{\sim}}(g_{2},h_{2})$
if and only if both $\langle g_{1},g_{2}\rangle$ and $\langle
h_{1},h_{2}\rangle$ are cyclic. Note that we may denote an element $(g,h)\in
G\times H$ simply by $gh$. We shall use that fact in the proof of the
following lemma.

###### Lemma 4.1

Let $\Gamma$ be a graph without any closed twins, let $G$ be a group, and let
$n$ be relatively prime to $\lvert G\rvert$. Then
$\mathcal{P}_{e}(G\times\mathbb{Z}_{n})$ is $\Gamma$-free if and only if
$\mathcal{P}_{e}(G)$ is $\Gamma$-free.

Proof. Since $\mathcal{P}_{e}(G)$ is an induced subgraph of
$\mathcal{P}_{e}(G\times\mathbb{Z}_{n})$, if
$\mathcal{P}_{e}(G\times\mathbb{Z}_{n})$ is $\Gamma$-free, then
$\mathcal{P}_{e}(G)$ is $\Gamma$-free as well. Therefore, it only remains to
show the other implication of the lemma.

Suppose now that $X\subseteq G\times\mathbb{Z}_{n}$ induces $\Gamma$ in
$\mathcal{P}_{e}(G\times\mathbb{Z}_{n})$. Let
$\pi_{1}:G\times\mathbb{Z}_{n}\rightarrow G$ denote the first projection, and
let $H=\pi_{1}(X)$. Let us prove that $\pi_{1}$ embeds $\Gamma$ into
$\mathcal{P}_{e}(G)$. Suppose the opposite, i.e. that $(h,k),(h,l)\in X$ for
some $h\in H$ and $k,l\in\mathbb{Z}_{n}$, $k\neq l$. Let $(g,m)\in
G\times\mathbb{Z}_{n}$. Then, by [36, Lemma 2.1],

$\displaystyle\langle hk,gm\rangle\text{ is cyclic }$
$\displaystyle\Leftrightarrow\langle h,g\rangle\text{ and }\langle
k,m\rangle\text{ are cyclic}$ $\displaystyle\Leftrightarrow\langle
h,g\rangle\text{ and }\langle l,m\rangle\text{ are cyclic}$
$\displaystyle\Leftrightarrow\langle hl,gm\rangle\text{ is cyclic.}$

Therefore, $hk$ and $hl$ have the same closed neighborhood in
$\mathcal{P}_{e}(G\times\mathbb{Z}_{n})$, which implies that they have the
same closed neighborhood in $\Gamma$. However, since no pair of vertices of
$\Gamma$ have same closed neighborhoods, it follows that $(h,k)=(h,l)$. Thus,
we have obtained a contradiction, and therefore, we have shown that $\pi_{1}$
embeds $\Gamma$ into $\mathcal{P}_{e}(G)$. This completes the proof that
$\mathcal{P}_{e}(G)$ contains $\Gamma$ as an induced graph. $\hfill\Box\vskip
6.0pt plus 2.0pt minus 2.0pt$

###  4.1 Nilpotent groups

In this subsection, we focus on nilpotent groups. Before proving the main
result, we need to show the following lemma first.

###### Lemma 4.2

Let $G$ be a nilpotent group. Then the following are equivalent:

  1. (a)

$G$ has at most one noncyclic Sylow subgroup;

  2. (b)

$\mathcal{P}_{e}(G)$ is $P_{4}$-free;

  3. (c)

$\mathcal{P}_{e}(G)$ is $C_{4}$-free.

Proof. Let us show first that any of (b) and (c) implies (a). Let $P$ and $Q$
be two distinct noncyclic Sylow subgroups of $G$. Then $P\times Q$ is a
subgroup of $G$. Note that the orders of $|P|$ and $|Q|$ are relatively prime.
Since $P$ is not cyclic, neither is $\mathcal{P}_{e}(P)$ complete. Therefore,
there are $x_{1},x_{2}\in P$ that are nonadjacent in $\mathcal{P}_{e}(P)$.
Similarly, there are $y_{1},y_{2}\in Q$ nonadjacent in $\mathcal{P}_{e}(Q)$.
Then, by [36, Lemma 2.1], $x_{1}\stackrel{{\scriptstyle
e}}{{\sim}}y_{1}\stackrel{{\scriptstyle
e}}{{\sim}}x_{2}\stackrel{{\scriptstyle e}}{{\sim}}x_{2}y_{2}$ is an induced
path of length four in $\mathcal{P}_{e}(G)$, and $x_{1}\stackrel{{\scriptstyle
e}}{{\sim}}y_{1}\stackrel{{\scriptstyle
e}}{{\sim}}x_{2}\stackrel{{\scriptstyle
e}}{{\sim}}y_{2}\stackrel{{\scriptstyle e}}{{\sim}}x_{1}$ is an induced cycle
of length four in $\mathcal{P}_{e}(G)$.

It remains now to show that (a) implies (b) and (c). Let us show first that
the enhanced power graph of a finite $p$-group is $P_{4}$-free and
$C_{4}$-free. Suppose that, for a $p$-group $P$, elements $x,y,z,w\in P$
induce the path $x\stackrel{{\scriptstyle e}}{{\sim}}y\stackrel{{\scriptstyle
e}}{{\sim}}z\stackrel{{\scriptstyle e}}{{\sim}}w$ or the cycle
$x\stackrel{{\scriptstyle e}}{{\sim}}y\stackrel{{\scriptstyle
e}}{{\sim}}z\stackrel{{\scriptstyle e}}{{\sim}}w\stackrel{{\scriptstyle
e}}{{\sim}}x$ in $\mathcal{P}_{e}(P)$. Then $y\in\langle z\rangle$ or
$z\in\langle y\rangle$, so let us assume, without loss of generality, that
$y\in\langle z\rangle$. Then $z\in\langle x\rangle$ or $x,z\in\langle
y\rangle$, which implies that $x\stackrel{{\scriptstyle e}}{{\sim}}z$, which
is a contradiction. Therefore, the enhanced power graph of any finite
$p$-group is a cograph. Therefore, by Lemma 4.1, (a) does imply (b) and (c)
since $P_{4}$ and $C_{4}$ contain no closed twins. $\hfill\Box\vskip 6.0pt
plus 2.0pt minus 2.0pt$

Now, we are ready to prove the main result of this subsection.

###### Theorem 4.3

The following are equivalent for any nilpotent group $G$:

  1. (a)

$\mathcal{P}_{e}(G)$ is a chordal graph;

  2. (b)

$\mathcal{P}_{e}(G)$ is a cograph;

  3. (c)

$G$ has at most one noncyclic Sylow subgroup;

  4. (d)

$G\cong P\times\mathbb{Z}_{n}$, where $P$ is a $p$-group for some $p$
relatively prime to $n$.

Proof. Clearly, conditions (c) are (d) are equivalent because every finite
nilpotent group is the direct product of its Sylow subgroups.

Let us remind ourselves that a graph is a cograph if and only if it is
$P_{4}$-free. Therefore, by Lemma 4.2, conditions (a), (b), and (c) are
equivalent. This proves the theorem. $\hfill\Box\vskip 6.0pt plus 2.0pt minus
2.0pt$

###### Corollary 4.4

The enhanced power graph of a finite $p$-group is a chordal graph, as well as
a cograph.

###### Remark 4.5

By Theorem 4.3 and Lemma 2.1, if $G$ contains a nilpotent subgroup which has
at least two distinct noncyclic Sylow subgroups, then $\mathcal{P}_{e}(G)$ is
neither a chordal graph nor a cograph. For example, if $G$ has a subgroup
isomorphic to $\mathbb{Z}_{6}\times\mathbb{Z}_{6}$, then $\mathcal{P}_{e}(G)$
is neither a chordal graph nor a cograph.

Also, notice that some of the classes of graphs from Diagram 1 are
incomparable, such as cographs and chordal graphs. Interestingly however, by
[36, Theorem 6.2] and Theorems 3.3 and 4.3, if we observe, instead of all
graphs, only enhanced power graphs of finite nilpotent groups, we obtain the
following relations between families of those graphs.

$\displaystyle\text{threshold graphs}\subseteq\text{split
graphs}\subseteq\text{chordal graphs}=\text{cographs}\subseteq\text{perfect
graphs}$

###  4.2 Non-nilpotent groups

In this subsection, we give some families of non-nilpotent groups whose
enhanced power graphs are chordal graphs and cographs (see Example 4.7 and
Propositions 4.8, 4.11, 4.13, and 4.14). First, we give a sufficient condition
for a finite group whose enhanced power graph is chordal and a cograph. Let us
remind the reader that $\mathcal{M}(G)$ denotes the set of all maximal cyclic
subgroups of $G$.

###### Proposition 4.6

Let $G$ be a group. Let $k$ be a number such that the intersections of any two
distinct maximal cyclic subgroups has cardinality $k$, then
$\mathcal{P}_{e}(G)$ is a chordal graph as well as a cograph.

Proof. Let $U=M\cap N$ for some $M,N\in\mathcal{M}(G)$. Since the intersection
of two cyclic subgroups is a cyclic subgroup, $U$ is a cyclic subgroup $G$.
Let $X$ and $Y$ be any maximal cyclic subgroups of $G$. We want to show now
that $X\cap Y=U$. $X\cap M$ is also a cyclic subgroup of $M$ of order $k$.
Because $M$ has the unique subgroup of order $K$, it follows that $U=X\cap M$.
Similarly, as $X$ has the unique subgroup of order $k$, we obtain $X\cap
Y=X\cap M=U$. Therefore, the intersection of any pair of distinct maximal
cyclic subgroups of $G$ is $U$.

Suppose, for contradiction, that $x,y,y,w\in G$ induce a path
$x\stackrel{{\scriptstyle e}}{{\sim}}y\stackrel{{\scriptstyle
e}}{{\sim}}z\stackrel{{\scriptstyle e}}{{\sim}}w$ or a cycle
$x\stackrel{{\scriptstyle e}}{{\sim}}y\stackrel{{\scriptstyle
e}}{{\sim}}z\stackrel{{\scriptstyle e}}{{\sim}}w\stackrel{{\scriptstyle
e}}{{\sim}}x$ in $\mathcal{P}_{e}(G)$. Notice that elements of $U$ are
adjacent to all elements of $G$ in $\mathcal{P}_{e}(G)$. Therefore, $U$
contains none of $x$, $y$, $z$, and $w$ since, otherwise, $\\{x,y,z,w\\}$
would not induce $P_{4}$ nor $C_{4}$. Let us denote two maximal cyclic
subgroups that contain $\langle x,y\rangle$ and $\langle y,z\rangle$ by $K$
and $L$, respectively. Since $x\not\stackrel{{\scriptstyle e}}{{\sim}}z$, it
follows that $K\neq L$. However, $K\neq L$ implies that $y\in K\cap L\subseteq
U$, which is a contradiction. Thus, $\mathcal{P}_{e}(G)$ is both $P_{4}$-free
and $C_{4}$-free, and therefore, it is a chordal graph and a cograph.
$\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

Notice that, for a group $G$, the condition from Proposition 4.6 is equivalent
to $G$ having a cyclic subgroup $C$ such that $C=M\cap N$ for every
$M,N\in\mathcal{M}(G)$, $M\neq N$.

In a dihedral group, the intersection of any two distinct maximal cyclic
subgroups is the trivial group. Also, a generalized quaternion group has the
unique subgroup of order $2$, which is the intersection of every two distinct
maximal cyclic subgroups. Therefore, by Proposition 4.6, we obtain the
following which conclude that the enhanced power graph of any dihedral group
or any generalized quaternion group is cograph and a chordal graph.

###### Example 4.7

The enhanced power graph of every dihedral group and every generalized
quaternion group is chordal and a cograph.

Let us remark that $D_{2n}$ and $Q_{4n}$ are nilpotent only if $n$ is a power
of $2$.

A group is called a $P$-group [17] if every nonidentity element of the group
has prime order. For example, $D_{2q}$ is a $P$-group for any odd prime $q$. A
group is called a CP-group [24] if every nontrivial element of the group has
prime power order. For example, any $p$-group is a $CP$-group, and
$D_{2q^{n}}$ is a $CP$-group for any prime $q$ and positive integer $n$.
Clearly, a $P$-group is also a $CP$-group. By Proposition 4.6, we see that for
each $P$-group $G$, $\mathcal{P}_{e}(G)$ is a chordal graph as well as a
cograph. Moreover, we have the following result.

###### Proposition 4.8

The enhanced power graph of any $CP$-group is a chordal graph as well as a
cograph.

Proof. Let $G$ be a $CP$-group. Suppose that some elements $x,y,z,w\in G$
induce the path $x\stackrel{{\scriptstyle e}}{{\sim}}y\stackrel{{\scriptstyle
e}}{{\sim}}z\stackrel{{\scriptstyle e}}{{\sim}}w$ or the cycle
$x\stackrel{{\scriptstyle e}}{{\sim}}y\stackrel{{\scriptstyle
e}}{{\sim}}z\stackrel{{\scriptstyle e}}{{\sim}}w\stackrel{{\scriptstyle
e}}{{\sim}}x$ in $\mathcal{P}_{e}(G)$. Notice that $e\not\in\\{x,y,z,w\\}$
since the identity $e$ is adjacent to all vertices of $\mathcal{P}_{e}(G)$.
Therefore, orders of $x$, $y$, $z$ and $w$ are powers of some prime $p$.
Without loss of generality, we may assume that $z\in\langle y\rangle$. Then
$x\stackrel{{\scriptstyle e}}{{\sim}}z$ since either $x,z\in\langle y\rangle$
or $z\in\langle y\rangle\leq\langle x\rangle$. This contradicts the fact that
$x$, $y$, $z$ and $w$ induce is a path or a cycle. Thus, $\mathcal{P}_{e}(G)$
is $P_{4}$-free and $C_{4}$-free, and therefore, $\mathcal{P}_{e}(G)$ is
chordal and a cograph. $\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

The prime graph of a finite group $G$ is a simple graph whose vertex set
consists of all prime divisors of $|G|$ and whose two distinct vertices $p$
and $q$ are adjacent if $G$ has an element of order $pq$. The prime graph of a
group was first introduced by Gruenberg and Kegel in an unpublished manuscript
studying integral representations of groups in 1975. It is clear that, for a
group $G$, its prime graph is a null graph if and only if $G$ is a $CP$-group.
Thus, we have the following corollary.

###### Corollary 4.9

Let $G$ be a group with null prime graph. Then $\mathcal{P}_{e}(G)$ is a
chordal graph as well as a cograph.

$CP$-groups were studied in [18, 35, 34]. All nonabelian simple $CP$-groups
were classified by Suzuki [35]. By [35], we have the following result.

###### Example 4.10

If $G$ is isomorphic to $Sz(8)$, $Sz(32)$, $PSL(3,4)$, or $PSL(2,q)$ for some
$q\in\\{5,7,8,9,17\\}$, then $\mathcal{P}_{e}(G)$ is a chordal graph as well
as a cograph.

In the remainder of this subsection, we classify all symmetric groups and all
alternative groups whose enhanced power graph is a cograph and a chordal
graph. Note that $S_{n}$ is non-nilpotent for every $n\geq 3$.

###### Proposition 4.11

The following conditions are equivalent.

  1. (a)

$\mathcal{P}_{e}(S_{n})$ is a cograph;

  2. (b)

$\mathcal{P}_{e}(S_{n})$ is a chordal graph;

  3. (c)

$n\leq 5$.

Proof. Let us observe the subgraph of $\mathcal{P}_{e}(S_{6})$ induced by $(1\
2)$, $(3\ 4\ 5)$, $(1\ 6)$, and $(2\ 3\ 4)$. Notice that the subgroup
generated by a pair of disjoint cyclic permutations of relatively prime orders
is cyclic. On the other hand, if a pair cyclic permutations does not commute,
they do not generate a cyclic subgroup. However, although a pair of disjoint
cyclic permutations of the same order commute, they do not generate a cyclic
subgroup either. Therefore,

$(1\ 2)\stackrel{{\scriptstyle e}}{{\sim}}(3\ 4\ 5)\stackrel{{\scriptstyle
e}}{{\sim}}(1\ 6)\stackrel{{\scriptstyle e}}{{\sim}}(2\ 3\ 4)$

is an induced path in $\mathcal{P}_{e}(S_{6})$, and thus,
$\mathcal{P}_{e}(S_{6})$ is not a cograph. Therefore, by Lemma 2.1, (a)
implies (c).

Similarly, notice that

$\begin{gathered}(1\ 2\ 3)\stackrel{{\scriptstyle e}}{{\sim}}(5\
6)\stackrel{{\scriptstyle e}}{{\sim}}(2\ 3\ 4)\stackrel{{\scriptstyle
e}}{{\sim}}(6\ 1)\stackrel{{\scriptstyle e}}{{\sim}}(3\ 4\
5)\stackrel{{\scriptstyle e}}{{\sim}}(1\ 2)\stackrel{{\scriptstyle
e}}{{\sim}}(4\ 5\ 6)\\\ \stackrel{{\scriptstyle e}}{{\sim}}(2\
3)\stackrel{{\scriptstyle e}}{{\sim}}(5\ 6\ 1)\stackrel{{\scriptstyle
e}}{{\sim}}(3\ 4)\stackrel{{\scriptstyle e}}{{\sim}}(6\ 1\
2)\stackrel{{\scriptstyle e}}{{\sim}}(4\ 5)\stackrel{{\scriptstyle
e}}{{\sim}}(1\ 2\ 3)\end{gathered}$

is an induced cycle of $\mathcal{P}_{e}(S_{6})$. Therefore,
$\mathcal{P}_{e}(S_{6})$ is not chordal either. Thus, by Lemma 2.1, (b)
implies (c).

It remains for us to show that (c) implies (a) and (b). Suppose that $n\leq
5$, and suppose that $\mathcal{P}_{e}(S_{n})$ contains elements $x$, $y$, $z$,
and $w$ which induce the path $x\stackrel{{\scriptstyle
e}}{{\sim}}y\stackrel{{\scriptstyle e}}{{\sim}}z\stackrel{{\scriptstyle
e}}{{\sim}}w$ or the cycle $x\stackrel{{\scriptstyle
e}}{{\sim}}y\stackrel{{\scriptstyle e}}{{\sim}}z\stackrel{{\scriptstyle
e}}{{\sim}}w\stackrel{{\scriptstyle e}}{{\sim}}x$. Notice that, in a path and
in a cycle, no pair of vertices have the same closed neighborhood. Therefore,
none of $x$, $y$, $z$, and $w$ is a cyclic permutation of order $5$ or $4$,
and none of them is the product of two transpositions, since, for a cyclic
permutation $c$ of order $5$ or $4$, $[c]_{\stackrel{{\scriptstyle
e}}{{\equiv}}}=\langle c\rangle\setminus\\{e\\}$. Thus, $\\{x,y,z,w\\}$
contains only cyclic permutations of order $3$ and transpositions. Without
loss of generality, let $o(y)=3$. But a cyclic permutation of order $3$
commutes with at most one transposition in $S_{n}$, $n\leq 5$. Thus, we have
obtained a contradiction, and we conclude that $\mathcal{P}_{e}(S_{n})$ is
$P_{4}$-free and $C_{4}$-free for $n\leq 5$. This finishes our proof.
$\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

###### Remark 4.12

In the above proof, the length of the presented induced cycle in
$\mathcal{P}_{e}(S_{6})$ is $12$. However, $\mathcal{P}_{e}(S_{6})$ does
contain an induced cycle of length $6$. In particular,

$\begin{gathered}(1\ 2)(3\ 4)(5\ 6)\stackrel{{\scriptstyle e}}{{\sim}}(1\ 4\
5)(2\ 3\ 6)\stackrel{{\scriptstyle e}}{{\sim}}(1\ 3)(2\ 5)(4\
6)\stackrel{{\scriptstyle e}}{{\sim}}(1\ 5\ 6)(2\ 4\ 3)\\\
\stackrel{{\scriptstyle e}}{{\sim}}(1\ 4)(2\ 6)(3\ 5)\stackrel{{\scriptstyle
e}}{{\sim}}(1\ 6\ 3)(2\ 5\ 4)\stackrel{{\scriptstyle e}}{{\sim}}(1\ 2)(3\
4)(5\ 6)\end{gathered}$

is one such induced cycle. Although that fact may be easier to verify for the
induced cycle from the proof of Lemma 4.11 than for the above-mentioned one.
Moreover, one can show that $6$ is the smallest length of an induced cycle in
$\mathcal{P}_{e}(S_{6})$.

Furthermore, for any $n\geq 7$, $\mathcal{P}_{e}(S_{n})$ contains an induced
cycle of length $4$, e.g.

$(1\ 2\ 3)\stackrel{{\scriptstyle e}}{{\sim}}(4\ 5)\stackrel{{\scriptstyle
e}}{{\sim}}(1\ 2\ 7)\stackrel{{\scriptstyle e}}{{\sim}}(4\
6)\stackrel{{\scriptstyle e}}{{\sim}}(1\ 2\ 3).$

Now, we turn our attention to alternating groups. It is well known that
$A_{n}$ is a simple group for each $n\geq 5$. Also, note that $A_{n}$ is non-
nilpotent for every $n\geq 4$.

###### Proposition 4.13

$\mathcal{P}_{e}(A_{n})$ is a cograph if and only if $n\leq 6$.

Proof. Notice that

$(1\ 2)(3\ 4)\stackrel{{\scriptstyle e}}{{\sim}}(5\ 6\
7)\stackrel{{\scriptstyle e}}{{\sim}}(1\ 3)(2\ 4)\stackrel{{\scriptstyle
e}}{{\sim}}(1\ 2\ 3\ 4)(5\ 6)$

is an induced path in $\mathcal{P}_{e}(A_{7})$. Namely, $(1\ 3)(2\
4)=\big{(}(1\ 2\ 3\ 4)(5\ 6)\big{)}^{2}$, and as discussed in the proof of
Proposition 4.11, disjoint permutations of relatively prime orders generate
cyclic subgroups, and any pair of elements of a cyclic subgroup commutes. By
Lemma 2.1, this proves one implication of the proposition.

In order to prove the other implication as well, notice that $A_{6}$ is a
$CP$-group. Then, by Proposition 4.8, $\mathcal{P}_{e}(A_{6})$ is a cograph.
Therefore, $\mathcal{P}_{e}(A_{n})$ is a cograph for every $n\leq 6$. This
completes the proof. $\hfill\Box\vskip 6.0pt plus 2.0pt minus 2.0pt$

###### Proposition 4.14

$\mathcal{P}_{e}(A_{n})$ is a chordal graph if and only if $n\leq 7$.

Proof. Notice that, for $n\geq 8$, $\mathcal{P}_{e}(A_{n})$ contains the
induced cycle

$(1\ 2)(3\ 4)\stackrel{{\scriptstyle e}}{{\sim}}(5\ 6\
7)\stackrel{{\scriptstyle e}}{{\sim}}(1\ 3)(2\ 4)\stackrel{{\scriptstyle
e}}{{\sim}}(5\ 6\ 8)\stackrel{{\scriptstyle e}}{{\sim}}(1\ 2)(3\ 4)$

of length four.

By Lemma 2.1, it now suffices to prove that $\mathcal{P}_{e}(A_{7})$ has no
induced cycles of length at least $4$. Suppose, for contradiction, that
$\cdots\stackrel{{\scriptstyle e}}{{\sim}}x\stackrel{{\scriptstyle
e}}{{\sim}}y\stackrel{{\scriptstyle e}}{{\sim}}z\stackrel{{\scriptstyle
e}}{{\sim}}w\stackrel{{\scriptstyle e}}{{\sim}}\cdots$ is an induced cycle of
$\mathcal{P}_{e}(A_{7})$, where $x,y,z,w$ are pairwise distinct. Notice that
$\pi_{e}(A_{7})=\\{1,2,3,4,5,6,7\\}$. It follows that each of
$o(x),o(y),o(z),o(w)$ is $2$ or $3$. Without loss of generality, let $o(y)=2$
and let $y=(1\ 2)(3\ 4)$. Then $x,z\in\\{(5\ 6\ 7),(5\ 7\
6)\\}\subseteq\langle(5\ 6\ 7)\rangle$, which implies that $x$ is adjacent to
$z$. Thus, we have obtained a contradiction. $\hfill\Box\vskip 6.0pt plus
2.0pt minus 2.0pt$

###  4.3 Small groups

In this subsection, we describe some classes of groups whose enhanced power
graphs are chordal graphs and cographs. Further, we determine the only two
groups of order at most $24$ whose enhanced power graph is not a cograph. We
also show the minimal order of a group with non-chordal enhanced power graph
is $36$.

The following result is an immediate consequence of Lemma 4.1, since neither
$P_{4}$ nor a cycle of length at least $4$ has closed twins.

###### Corollary 4.15

Let $G$ be a group of order relatively prime to $n$. Then
$\mathcal{P}_{e}(G\times\mathbb{Z}_{n})$ is a cograph (resp. a chordal graph)
if and only if $\mathcal{P}_{e}(G)$ is a cograph (resp. a chordal graph).

Notice that a group whose order is a product of two distinct primes is either
a cyclic or a $CP$-group. Therefore, by Proposition 4.8, we have the following
result.

###### Proposition 4.16

If $|G|$ is a product of two distinct primes, then $\mathcal{P}_{e}(G)$ is a
chordal graph as well as a cograph.

Before heading to the next lemma, we note that the cyclicizer of a group $G$,
denoted by ${\rm Cyc}(G)$, is defined by

${\rm Cyc}(G)=\\{g\in G:\langle g,x\rangle\text{ is cyclic for any $x\in
G$}\\}.$

Some authors, e.g. [31], also call it cycel of a group.

###### Proposition 4.17

Let $G$ be a group and let $p,q$ be distinct prime numbers. Then
$\mathcal{P}_{e}(G)$ is a chordal graph as well as a cograph if one of the
following holds:

  1. (a)

$\pi_{e}(G)=\\{1,p,q,pq\\}$ and $G$ has the unique subgroup of order $p$ or
$q$;

  2. (b)

$\pi_{e}(G)=\\{1,p,q,pq\\}$ 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$;

  3. (c)

$\pi_{e}(G)=\\{1,p,q,pq,p^{2}\\}$ and either $G$ has a unique cyclic subgroup
of order $pq$, or the intersection of all cyclic subgroups of order $pq$ is
$\langle a\rangle$ where $a\in{\rm Cyc}(G)$ and $o(a)\in\\{p,q\\}$.

Proof. In order to prove this lemma, let us suppose that $x$, $y$, $z$, and
$w$ induce the path $x\stackrel{{\scriptstyle
e}}{{\sim}}y\stackrel{{\scriptstyle e}}{{\sim}}z\stackrel{{\scriptstyle
e}}{{\sim}}w$ or the cycle $x\stackrel{{\scriptstyle
e}}{{\sim}}y\stackrel{{\scriptstyle e}}{{\sim}}z\stackrel{{\scriptstyle
e}}{{\sim}}w\stackrel{{\scriptstyle e}}{{\sim}}x$ in $\mathcal{P}_{e}(G)$.
Further, we will suppose that (a), (b), and (c) hold, respectively, find a
contradiction in each of the cases. Thus, we shall prove the lemma.

(a) Let $\pi_{e}(G)=\\{1,p,q,pq\\}$, and, without loss of generality, let $G$
have the unique subgroup of order $p$. It follows that
$\\{o(y),o(z)\\}=\\{p,q\\}$. Without loss of generality, let $o(y)=p$ and
$o(z)=q$. Then $o(w)\not\in\\{p,q\\}$, and therefore, $o(w)=pq$. Thus,
$\langle y\rangle\leq\langle w\rangle$, since $\langle y\rangle$ is the unique
cyclic subgroup of order $p$. Therefore, $y\stackrel{{\scriptstyle
e}}{{\sim}}w$, which is a contradiction.

(b) Let $\pi_{e}(G)=\\{1,p,q,pq\\}$, and suppose that $G$ has a unique cyclic
subgroup of order $pq$. Then $y$ and $z$ have prime orders. Without loss of
generality, let $o(y)=p$ and $o(z)=q$. It follows that $o(w)\in\\{p,pq\\}$.
Since $G$ has a unique cyclic subgroup of order $pq$, then $\langle
w,z\rangle=\langle y,z\rangle$ is the unique cyclic subgroup of order $pq$,
which implies that $y\stackrel{{\scriptstyle e}}{{\sim}}w$. Thus we have
obtained a contradiction.

Now, let $\pi_{e}(G)=\\{1,p,q,pq\\}$, and let the intersection of all cyclic
subgroups of order $pq$ has size $p$ or $q$. Again, $o(y),o(z)\in\\{p,q\\}$,
and we can assume without loss of generality that $o(y)=p$ and $o(z)=q$. Since
the intersection of all cyclic subgroups of order $pq$ has size $p$, then $y$
belongs to the cyclic subgroup $\langle w,z\rangle$ of order $pq$. Therefore,
$y\stackrel{{\scriptstyle e}}{{\sim}}w$, which is a contradiction.

(c) Suppose that $\pi_{e}(G)=\\{1,p,q,pq,p^{2}\\}$ and that $G$ has a unique
cyclic subgroup of order $pq$. Since elements $y$ and $z$ have prime orders,
we may, without loss of generality, assume that $o(y)=p$ and $o(z)=q$. Then
$o(w)\in\\{p,pq\\}$. Note that $\langle y,z\rangle$ is a cyclic subgroup of
order $pq$. Since $G$ has a unique cyclic subgroup of order $pq$, then clearly
$y\stackrel{{\scriptstyle e}}{{\sim}}w$, which is a contradiction.

Now, let $\pi_{e}(G)=\\{1,p,q,pq,p^{2}\\}$, and let, without loss of
generality, the intersection of all cyclic subgroups of order $pq$ be $\langle
a\rangle$ where $a\in{\rm Cyc}(G)$ and $o(a)=p$. Also, $y$ and $z$ have prime
orders. Without loss of generality, let $o(y)=p$ and $o(z)=q$. Then $y\in{\rm
Cyc}(G)$, which implies that $y\stackrel{{\scriptstyle e}}{{\sim}}w$. Thus, we
have obtained a contradiction. This proves the lemma. $\hfill\Box\vskip 6.0pt
plus 2.0pt minus 2.0pt$

###### Example 4.18

$\mathbb{Z}_{2}\times\mathbb{Z}_{2}\times S_{3}$, $\mathbb{Z}_{3}\times S_{3}$
and $SL(2,3)$ satisfy the conditions (a), (b) and (c) of Proposition 4.17,
respectively.

By GAP [22], we have determined that the minimal size of a group with non-
chordal enhanced power graph is $36$. In particular, Theorem 4.3 implies that
$\mathcal{P}_{e}(\mathbb{Z}_{6}\times\mathbb{Z}_{6})$ is not chordal. Even
though the enhanced power graph of a finite nilpotent group is chordal if and
only if it is a cograph by Theorem 4.3, that is not the case for finite groups
in general. Using GAP, we have determined that the minimal size of a group
whose enhanced power graph is not a cograph is $24$. Namely, the two such
groups of order $24$ are $Q_{12}\times\mathbb{Z}_{2}$ and the semidirect
product $Q_{8}\rtimes\mathbb{Z}_{3}$ with action kernel
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$.

Acknowledgements The first author’s research is supported by National Natural
Science Foundation of China (Grant No. 11801441). The second author
acknowledges financial support of the Ministry of Education, Science and
Technological Development of the Republic of Serbia (Grant No.
451-03-68/2022-14/200125). The fourth author’s research is supported by
National Natural Science Foundation of China (Grant No. 61976244).

## References

  * [1] G. Aalipour, S. Akbari, P.J. Cameron, R. Nikandish, F. Shaveisi, On the structure of the power graph and the enhanced power graph of a group, Electron. J. Combin. 24 (2017), #P3.16
  * [2] J. Abawajy, A. Kelarev, M. Chowdhury, Power graphs: A survey, Electron. J. Graph Theory Appl. 1 (2013), 125–147
  * [3] A. Abdollahi, A. Mohammadi Hassanabadi, Noncyclic Graph of a Group, Communications in Algebra 35 (2007), no. 7, 2057–2081.
  * [4] M. Afkhami, A. Jafarzadeh, K. Khashyarmanesh, S. Mohammadikhah, On cyclic graphs of finite semigroups, Journal of Algebra and Its Applications 13 (2014), no. 7, 1450035
  * [5] S. Bera, A.K. Bhuniya, On enhanced power graphs of finite groups, J. Algebra Appl. 17 (2018), 1850146
  * [6] S. Bera, H.K. Dey, S.K. Mukherjee, On the connectivity of enhanced power graphs of finite groups, Graphs Combin. 37 (2021), 591–603
  * [7] I. Bošnjak, R. Madarász, S. Zahirović, Some new results concerning power graphs and enhanced power graphs of groups, arXiv:2012.02851
  * [8] D. Bubboloni, M.A. Iranmanesh, S.M. Shaker, Quotient graphs for power graphs, Rend. Semin. Mat. Univ. Padova 138 (2017), 61–89
  * [9] P.J. Cameron, Graphs defined on groups, Int. J. Group Theory 11 (2022), 53–107
  * [10] P.J. Cameron, The power graph of a finite group, II, J. Group Theory 13 (2010), 779–783
  * [11] P.J. Cameron, S. Ghosh, The power graph of a finite group, Discrete Math. 311 (2011), 1220–1222
  * [12] P.J. Cameron, B. Kuzma, Between the enhanced power graph and the commuting graph, Journal of Graph Theory (2022), doi: 10.1002/jgt.22871
  * [13] I. Chakrabarty, S. Ghosh, M.K. Sen, Undirected power graphs of semigroups, Semigroup Forum 78 (2009), 410–426
  * [14] D.G. Costanzo, M.L. Lewis, S. Schmidt, E. Tsegaye, G. Udell, The cyclic graph (deleted enhanced power graph) of a direct product, Involve 14 (2021), 167–179
  * [15] D.G. Costanzo, M.L. Lewis, S. Schmidt, E. Tsegaye, G. Udell, The cyclic graph of a $Z$-group, Bull. Aust. Math. Soc. 104 (2021), 295–301
  * [16] S. Dalal, J. Kumar, On enhanced power graphs of certain groups, Discrete Math. Algorithms Appl. 13 (2021), 2050099
  * [17] M. Deaconescu, Classification of finite groups with all elements of prime order, Proc. Amer. Math. Soc. 106 (1989), 625–629.
  * [18] A.L. Delgado, Y.F. Wu, On locally finite groups in which every element has prime power order, Illinois J. Math. 46 (2002), 885–891
  * [19] A. Doostabadi, A. Erfanian, M. Farrokhi D.G., On power graphs of finite groups with forbidden induced subgraphs, Indag. Math. (NS) 25 (2014), 525–533
  * [20] M. Feng, X. Ma, K. Wang, The structure and metric dimension of the power graph of a finite group, Eur. J. Combin. 43 (2015), 82–97
  * [21] S. Foldes, P.L. Hammer, Split graphs, in: Proceedings of the $8$th South-Eastern Conference on Combinatorics, Graph Theory and Computing, 1977, 311–315
  * [22] GAP – Groups, Algorithms, Programming – a System for Computational Discrete Algebra, Version 4.6.5, 2013, http://gap-system.org
  * [23] D. Gorenstein, Finite Groups, Chelsea Publishing Co., New York, 1980
  * [24] G. Higman, Finite groups in which every element has prime power order, J. Lond. Math. Soc. 32 (1957), 335–342
  * [25] A.V. Kelarev, S.J. Quinn, A combinatorial property and power graphs of groups, Contrib. General Algebra 12 (2000), 229–235
  * [26] A. Kumar, L. Selvaganesh, P.J. Cameron, T. Tamizh Chelvam, Recent developments on the power graph of finite groups - a survey, AKCE Int. J. Graphs Comb. 18 (2021), 65–94
  * [27] X, Ma, Y. She, The metric dimension of the enhanced power graph of a finite group, J. Algebra Appl. 19 (2020), 2050020
  * [28] X. Ma, G.L. Walls, K. Wang, Power graphs of (non)orientable genus two, Commun. Algebra 47 (2019), 276–288
  * [29] X.L. Ma, H.Q. Wei, G. Zhong, The cyclic graph of a finite group, Algebra 2013 (2013), 7 pp.
  * [30] P. Manna, P.J. Cameron, R. Mehatari, Forbidden subgraphs of power graphs, Electron. J. Combin. 28 (2021), no. 3, #P3.4
  * [31] K. O’Bryant, D. Patrick, L. Smithline, E. Wepsic, Some facts about cycles and tidy groups, Tech. Rep. MS–TR 92–04, Rose–Hulman Institute of Technology, Terre Haute, Ind, USA, 1992
  * [32] J. Pan, X. Guo, Exchange property for resolving sets in power graphs, Eur. J. Combin. 81 (2019), 394–403
  * [33] R.P. Panda, S. Dalal, J. Kumar, On the enhanced power graph of a finite group, Commun. Algebra 49 (2021), 1697–1716
  * [34] R. Shen, W. Shi, X. Zou, A new characterization of finite groups in which every element has prime power order, Preprint, www.sajm-online.com/cpgroups.pdf
  * [35] M. Suzuki, On a class of doubly transitive groups, Ann. Math. 75 (1962), 105–145
  * [36] S. Zahirović, I. Bošnjak, R. Madarász, A study of enhanced power graphs of finite groups, J. Algebra Appl. 19 (2020), 2050062