# Matching in Power Graphs of Finite Groups

Peter J Cameron111School of Mathematics and Statistics, University of St
Andrews, North Haugh, St Andrews, Fife, KY16 9SS, UK<EMAIL_ADDRESS>ORCiD 0000-0003-3130-9505, Swathi V V222Department of Mathematics, National
Institute of Technology Calicut, Kozhikode - 673601, India;
<EMAIL_ADDRESS>and M S Sunitha333Department of Mathematics, National
Institute of Technology Calicut, Kozhikode - 673601, India<EMAIL_ADDRESS>
###### Abstract

The power graph $P(G)$ of a finite group $G$ is the undirected simple graph
with vertex set $G$, where two elements are adjacent if one is a power of the
other. In this paper, the matching numbers of power graphs of finite groups
are investigated. We give upper and lower bounds, and conditions for the power
graph of a group to possess a perfect matching. We give a formula for the
matching number for any finite nilpotent group. In addition, using some
elementary number theory, we show that the matching number of the enhanced
power graph $P_{e}(G)$ of $G$ (in which two elements are adjacent if both are
powers of a common element) is equal to that of the power graph of $G$.

Keywords: group, power graph, matching, enhanced power graph, perfect
matching.

Mathematics Subject Classification 2010: 05C25

##  1 Introduction

Associating graphs to algebraic structures is an interesting research topic.
Cayley graphs, intersection graphs, zero divisor graphs, commuting graphs and
power graphs are some examples of graphs constructed from semigroups and
groups.

The directed power graph was first proposed in 2002 by Kelarev and Quinn [10].
For a semigroup $S$ , the directed power graph $\overrightarrow{P}(S)$ is a
graph with vertex set $S$ and there exists an arc from the vertex $x$ to the
vertex $y$ if and only if $y=x^{n}$ for some natural number $n\in\mathbf{N}$.
Motivated by this, Chakrabarty et al. [6] defined the undirected power graph
of a semigroup. The undirected power graph $P(S)$ of a semigroup $S$ is a
graph whose vertex set is $S$ and the edge set consists of pairs of distinct
vertices $x$ and $y$ if $y=x^{j}$ or $x=y^{k}$ for some $j,k\in\mathbb{N}$.

Many fascinating results on directed and undirected power graphs of finite
semigroups and groups were established by several authors. The authors of [6]
proved that the power graphs of ﬁnite groups are always connected. The authors
also proved that the necessary and sufficient condition for $P(G)$ to be
complete is that $G$ is a finite cyclic group having order $1$ or $p^{i}$, for
some prime number $p$ and positive integer $i$.

Curtin and Pourgholi [7, 8] proved that power graphs of cyclic groups have the
largest clique and maximum number of edges, among all ﬁnite groups of a given
order.

In [5], the first author and Shamik Ghosh proved that finite abelian groups
having isomorphic power graphs are isomophic. They also showed that Klein-4
group is the only finite group whose automorphism group is isomorphic to that
of its power graph. In [4], the first author proved that finite groups having
isomorphic power graphs have isomorphic directed power graphs.

The chromatic number of power graphs of finite groups is investigated in [11]
and [13] and some results on the independence number of the same is proved in
[12].

A graph $\Gamma=(V,E)$ is an undirected simple graph $\Gamma$ with vertex set
$V$ and edge set $E$. A matching or independent edge set $M$ in a graph
$\Gamma$ is a set of edges in which no two of them share a common vertex. A
vertex is said to be matched (or saturated) if it is incident to one of the
edges in the matching. Otherwise the vertex is unmatched. A matching $M$ of a
graph $\Gamma$ is a maximal matching if it is not a subset of any other
matching in $\Gamma$. A matching that contains the largest possible number of
edges is called a maximum matching. The size of a maximum matching in a graph
$\Gamma$ is known as its matching number, which is denoted by $\mu(\Gamma)$. A
perfect matching is a matching which saturates all vertices of the graph.

Let $G$ be a finite group. Together with the power graph, the enhanced power
graph and the commuting graph are some of the examples of graphs whose vertex
set is $G$ and whose edges reflect the group structure in some way. In the
_enhanced power graph_ of $G$,denoted by $P_{e}(G)$, two vertices $x$ and $y$
are adjacent if and only if $\langle x,y\rangle$ is cyclic, and in the
_commuting graph_ $\mathop{\mathrm{Com}}(G)$ of $G$, two vertices are adjacent
if they commute.

We denote the order of a group $G$ by $|G|$, while for $a\in G$, the order of
the element $a$ is denoted by $o(a)$.

In this paper, we concentrate on finding matchings in the power graphs. We
investigate several class of groups to obtain groups whose power graphs have a
perfect matching. In particular, we find the size of a maximum matching in the
power graph of any abelian group. We also include some results we obtained on
the enhanced power graph as well as commuting graph. In particular, and a
little surprisingly, the power graph and enhanced power graph have the same
matching number.

##  2 A preliminary result

We begin this section by noting that a finite group $G$ of odd order has
matching number $(|G|-1)/2$; that is, a maximum matching leaves just one
vertex unmatched. To see this, note that, for any $x\in G$, if $x\neq 1$, then
$x\neq x^{-1}$ and $\\{x,x^{-1}\\}$ is an edge of $P(G)$; these edges form a
matching of the required size.

For groups of even order, we begin with the following observation.

######  Theorem 2.1.

Let $G$ be a group of even order. Let $T=\\{g\in G:g^{2}=1\\}$ be the set
consisting of the identity and the involutions in $G$. Let $X(G)$ be a graph
with vertex set $G$ with the property that every element of $G\setminus T$ is
joined to its inverse. Then there is a maximum-size matching in $G$ for which
the set of unmatched vertices is contained in $T$.

###### Proof.

Clearly $|T|>1$.

Take any matching $M$ of $X(G)$. We describe a transformation to another
matching $M^{\prime}$ such that either $|M^{\prime}|>|M|$, or
$|M^{\prime}|=|M|$ and the number of unmatched vertices not in $T$ is smaller
in $M^{\prime}$ than in $M$.

Suppose that $g$ is an unmatched vertex which is not in $T$. If $g^{-1}$ is
also unmatched then we can match $g$ to $g^{-1}$, increasing the size of the
matching. So suppose $g^{-1}$ is matched.

Put $g=g_{0}$. Let $g_{1}$ be the vertex matched to $g_{0}^{-1}$; let $g_{2}$
be the vertex matched to $g_{1}^{-1}$; and so on, as long as possible. The
process terminates when either $g_{m}^{-1}$ is unmatched, or $g_{m}\in T$.

In the first case, we replace the edges $\\{g_{0}^{-1},g_{1}\\}$,
$\\{g_{1}^{-1},g_{2}\\}$, …, $\\{g_{m-1}^{-1},g_{m}\\}$ with the edges
$\\{g_{0},g_{0}^{-1}\\}$, $\\{g_{1},g_{1}^{-1}\\}$,
…,$\\{g_{m},g_{m}^{-1}\\}$, and the size of the matching is increased by one.

In the second case, we replace the edges $\\{g_{0}^{-1},g_{1}\\}$,
$\\{g_{1}^{-1},g_{2}\\}$, …, $\\{g_{m-1}^{-1},g_{m}\\}$ with the edges
$\\{g_{0},g_{0}^{-1}\\}$, $\\{g_{1},g_{1}^{-1}\\}$, …,
$\\{g_{m-1},g_{m-1}^{-1}\\}$. The resulting matching has the same size, but we
have replaced the unmatched vertex $g_{0}\notin S$ by $g_{m}\in S$, so we have
decreased by one the number of unmatched vertices not in $T$.

Continuing this process, we find a matching of maximal size in which all
unmatched vertices belong to $T$. ∎

If a matching has the property of the theorem, and the identity is unmatched,
then we may add the edge $\\{1,t\\}$ to the matching, where $t$ is an
involution. So the following holds.

######  Corollary 2.2.

  1. (a)

Let $G$ be a group of even order. Then the size of a maximum matching in the
power graph or enhanced power graph of $G$ is at least $1+(|G|-|T|)/2$, where
$T$ consists of the identity and the involutions in $G$.

  2. (b)

If $G$ is a group with a unique involution, then $P(G)$ has a perfect
matching.

######  Remark 2.3.

Groups with a unique involution are known; see [1].

##  3 Upper and lower bounds

In this section, we describe upper and lower bounds for the matching number of
the power graph of a group of even order. First, an upper bound.

######  Theorem 3.1.

Let $G$ be a finite group of even order. Let $I(G)$ be the set of involutions
in $G$, and $O(G)$ the set of elements of odd order. Then

  1. (a)

any matching of $P(G)$ leaves at least $|I(G)|-|O(G)|$ vertices unmatched;

  2. (b)

if $G$ has a perfect matching, then $|I(G)|\leq|O(G)|$.

###### Proof.

Let $\Gamma$ be the induced subgraph of $P(G)$ on $G\setminus O(G)$ (the set
of elements of even order in $G$). For $t\in I(G)$, let

$C_{t}=\\{x\in G:t\in\langle x\rangle\\}.$

Note that elements of $C_{t}$ have even order, and no element of $G$ can lie
in more than one of these sets, since a cyclic group contains at most one
involution.

We will show that the sets $C_{t}$ for $t\in I(G)$ are connected components of
$\Gamma$, and that they all have odd cardinality. It follows from Tutte’s
$1$-factor theorem [17] that, if $P(G)$ has a perfect matching, then $|I(G)|$
(the number of odd components of the induced subgraph on $G\setminus O(G)$)
does not exceed $|O(G)|$. Moreover, the deficit form of the theorem shows
that, if $|I(G)|>|O(G)|$, there are at least $|I(G)|-|O(G)|$ vertices
uncovered in any matching.

Note that any element of $C_{t}$ is joined to $t$ in the power graph, so any
two elements of $C_{t}$ have distance at most $2$; thus $C_{t}$ is contained
in a connected component. Take an edge $\\{x,y\\}$ of the power graph
contained in $G\setminus O(G)$. Without loss of generality, $x$ is a power of
$y$. Suppose that $t$ is the involution in $\langle x\rangle$, so that $x\in
C_{t}$. Then $t\in\langle x\rangle\leq\langle y\rangle$, so also $y\in C_{t}$.
This shows that $C_{t}$ is a connected component of $\Gamma$.

Now all elements of $C_{t}\setminus\\{t\\}$ have order greater than $2$; so
they can be paired with their inverses, leaving only $t$ unpaired. So
$|C_{t}|$ is odd, as required. ∎

Now we give a lower bound.

######  Theorem 3.2.

Let $G$ be a finite group of even order. Let $S=I(G)$ be the set of
involutions in $G$, and $O(C_{G}(S))$ the set of elements of odd order which
commute with all involutions.

  1. (a)

There is a matching leaving at most $\max\\{0,|I(G)|-|O(C_{G}(S))|\\}$
vertices unmatched.

  2. (b)

If $|I(G)|\leq|O(C_{G}(S))|$, then $P(G)$ has a perfect matching.

###### Proof.

Let $n=|I(G)|$ and $m=|O(C_{G}(S))$. Suppose first that $m\geq n$. Suppose
first that $m\geq n$. We start as usual with the matching $M$ on $G$ in which
each element of order greater than $2$ is matched to its inverse, leaving the
identity and the involutions unmatched. In addition, we match the identity to
one of the involutions. This leaves $n-1$ unmatched involutions, and $m-1$
elements of odd order commuting with them, falling into $(m-1)/2$ inverse
pairs. So we can partition the unmatched involutions into $(n-1)/2$ pairs, and
choose an inverse pair of elements of odd order commuting with each pair of
involutions.

Let $u,v$ be involutions, and $x,x^{-1}$ the corresponding pair of elements of
odd order commuting with $u$ and $v$. In the given matching, we have edges
$\\{x,x^{-1}\\}$, $\\{ux,ux^{-1}\\}$, and $\\{vx,vx^{-1}\\}$. We delete these
and include instead the edges $\\{u,ux\\}$, $\\{v,vx^{-1}\\}$,
$\\{ux^{-1},x^{-1}\\}$ and $\\{vx,x\\}$. Now all previously matched elements
are still matched, and in addition $u$ and $v$ are matched.

Repeating for all pairs of involutions we obtain a perfect matching.

Now suppose that $m<n$. Proceeding as above, we can match $(m-1)/2$ pairs of
involutions with elements of odd order, leaving $n-m$ involutions unmatched,
as required. ∎

With these results we can calculate the matching number of the power graph of
a nilpotent group.

######  Theorem 3.3.

Let $G$ be nilpotent; let $I(G)$ and $O(G)$ be the sets of involutions and
elements of odd order respectively.

  1. (a)

If $|I(G)|<|O(G)|$, then $G$ has a perfect matching.

  2. (b)

Otherwise, a maximum matching leaves $|I(G)|-|O(G)|$ vertices unmatched.

###### Proof.

If $G$ is nilpotent, then the elements of odd order form a normal subgroup
$O(G)$, and $G\cong H\times O(G)$ where $H$ is a Sylow $2$-subgroup. So all
involutions commute with all elements of odd order. So the result follows from
Theorems 3.1 and 3.2. ∎

##  4 Related results

In this section we give some miscellanous related results.

###  4.1 Groups whose power graph has small matching number

######  Theorem 4.1.

For every positive integer $m$, there are only finitely many finite groups $G$
with $\mu(G)=m$, apart from elementary abelian $2$-groups (with $\mu(G)=1$);
such a group satisfies $|G|<8m+4$.

###### Proof.

If $|G|$ is odd, then $m=\mu(G)=(|G|-1)/2$, so $|G|=2m+1$. So suppose that
$|G|$ is even. Then $|O(C_{G}(S))|\geq 1$, and the number of vertices
uncovered in a maximum matching is $|G|-2m$. So

$|I(G)|-1\geq|G|-2m,$

whence $|I(G)\geq|G|-2m+1$. However, if $G$ is not elementary abelian, then
$|I(G)|<\frac{3}{4}|G|$ (This result is described in the literature as an
“easy exercise”). So $|G|<8m+4$. ∎

Using this, we can give the determination of groups whose power graph has
matching number $1$ or $2$. The _dihedral group_ $D_{n}$ is the group of order
$2n$ which is the symmetry group of a regular $n$-gon, for $n\geq 3$.

######  Theorem 4.2.

Let $G$ be a finite group.

  1. (a)

If $\mu(P(G))=1$, then $G$ is either an elementary abelian $2$-group or
$C_{3}$.

  2. (b)

If $\mu(P(G))=2$, then $G$ is one of the following groups: $C_{4}$, $C_{5}$,
$D_{3}$ or $D_{4}$.

###### Proof.

Part (a) follows immediately from the preceding theorem. For part (b), we know
that such a group has order at most $11$, and there are only a small number of
groups to analyse. ∎

###  4.2 Groups with few involutions

We have seen that, if $G$ has a unique involution, then $P(G)$ has a perfect
matching. We now extend this result.

######  Theorem 4.3.

Let $G$ be a group with exactly three involutions, not all pairs of which
commute. Then either $G\cong S_{3}$, or $P(G)$ has a perfect matching.

###### Proof.

Let $s,t,u$ be the involutions. If $s$ and $t$ do not commute, then $\langle
s,t\rangle$ is a dihedral group of order $2n$ containing $n$ involutions, with
$n\geq 3$; so we must have $n=3$, and $s,t,u$ are the involutions in a normal
subgroup of $G$ isomorphic to $S_{3}$. Now $S_{3}$ is a complete group: this
means that its centre and its outer automorphism group are both trivial. Hence
every extension of $S_{3}$ splits: that is, if $S_{3}$ is a normal subgroup of
$G$, then $G\cong S_{3}\times H$. See [15, Section 13.5]. Now $H$ contains no
involutions, so has odd order. If $|H|=1$, then $G\cong S_{3}$; otherwise
$H=O(C_{G}(S))$, and the result follows from Theorem 3.2. ∎

For a group $G$, since $E(P(G))\subseteq E(P_{e}(G))\subseteq
E(\mathop{\mathrm{Com}}(G))$, the possibility to have a perfect matching in
the commuting graph is greater as compared to the power graph. The following
theorem shows that, if the order of a group is much bigger than the number of
involutions in it, then its commuting graph has a perfect matching.

######  Proposition 4.4.

There is a function $F$ such that, if $G$ is a group of even order which has
exactly $n$ involutions, and $|G|\geq F(n)$, then the commuting graph of $G$
has a perfect matching.

###### Proof.

We take $F(n)=2n\cdot n!$. So let $G$ be a group with even order greater than
$2n\cdot n!$ and suppose that $G$ contains $n$ involutions. We begin with a
matching $M$ as follows: elements of order greater than $2$ are matched to
their inverses; the identity is mapped to one involution. If $n=1$ we are
finished, so suppose not.

The group $G$ acts by conjugation on the set $S$ of involutions. The kernel of
this action, which is $C_{G}(S)$, has index at most $n!$ in $G$, and so has
order at least $2n$; so , putting $X=C_{G}(S)\setminus(\\{1\\}\cup S)$, we
have $|X|\geq n-1$. Moreover, elements of $X$ have order greater than $2$, and
so are matched with their inverses in $M$; and $X$ is inverse-closed.

Pick $(n-1)/2$ inverse pairs in $X$, say $\\{x_{1},x_{2}\\}$, …,
$\\{x_{n-2},x_{n-1}\\}$. Let $t_{1},\ldots,t_{n-1}$ be the unmatched
involutions in $S$. Now delete the edges $\\{x_{2i-1},x_{2i}\\}$ from $M$ for
$i=1,\ldots,(n-1)/2$, and add the edges $\\{x_{1},t_{2}\\}$,
$\\{x_{2},t_{2}\\}$, …, $\\{x_{n-1},t_{n-1}\\}$ instead. (These are edges
since $t_{i}\in S$ and $x_{i}\in C_{G}(S)$.) The result is a perfect matching
$M^{\prime}$. ∎

The hypothesis in the above theorem is not enough in the case of power graphs,
since, the power graph of $C_{2^{n}}\times C_{2^{m}}$ has no perfect matching
even if we take $n$ and $m$ very large: the group has three involutions and
one element of odd order.

######  Proposition 4.5.

There is a function $F$ on the natural numbers with the following property:
Let $G$ be a finite group of even order, and $S$ the set of involutions in
$G$. Suppose that for every involution $u\in S$, there is an involution $v$ in
$S$ which does not commute with $u$. If $|G|\geq F(|S|)$, then the power graph
of $G$ has a perfect matching.

###### Proof.

Take $F(n)=n.n!$. Now $G$ acts by conjugation on $S$, so $|G:C_{G}(S)|\leq
n!$. Thus, $|C_{G}(S)|\geq n$. Now by hypothesis, no involution belongs to
$C_{G}(S)$, so $C_{G}(S)$ is a group of odd order. Thus the assumptions of
Theorem 3.2 are satisfied. ∎

###  4.3 Embedding in groups whose power graph has a perfect matching

######  Theorem 4.6.

Let $G$ be a finite group of even order, and suppose that the number of
elements of $G$ not matched in a matching of maximum size in $P(G)$ is $s$. If
$p$ is an odd prime greater than $s$, then $G\times C_{p}$ has a perfect
matching.

###### Proof.

Let $t_{1},\ldots,t_{s}$ be the elements unmatched in some matching of maximum
size in $P(G)$. We know that without loss of generality we can assume that
$t_{1},\ldots,t_{s}$ are involutions. (The set of unmatched vertices can be
taken to be a subset of $\\{g\in G:g^{2}=1\\}$, and the identity can be
matched to any other vertex.) Note that $s$ is even.

Take $p>s$, and let $x$ be a generator of $C_{p}$ in the group $G\times
C_{p}$. Let $A_{0}=\langle x\rangle\setminus\\{1\\}$, and for $1\leq i\leq s$
let $A_{i}=A_{0}t_{i}$. Each set $A_{i}$ for $0\leq i\leq s$ induces a
complete graph in $P(G\times C_{p})$, and we have all possible edges between
$A_{0}$ and $A_{i}$ for $i>0$. Moreover, $t_{i}$ is joined to every vertex in
$A_{i}$. Also, $|A_{i}|=p-1$ for all $i$.

Choose an edge from $t_{i}$ to a vertex in $A_{i}$ for each $i$ and add to the
matching on $G$. There remain $p-2$ unmatched vertices in $A_{i}$; choose one,
and match it to a vertex in $A_{0}$, using distinct vertices for different
$i$. This leaves $p-3$ unmatched vertices in $A_{i}$, an even number, and
$p-1-s$ unmatched vertices in $A_{0}$, also an even number since $s$ is even.
So we can extend the matching by pairing up the unmatched vertices in $A_{i}$
for all $i$.

Finally, the vertices not yet matched come in inverse pairs, since they lie
outside the union of the subgroups $G$ and $\langle xt_{i}\rangle$; so we can
match each remaining vertex with its inverse.

∎

As a companion piece we have the following:

######  Theorem 4.7.

Let $G$ be a finite group of odd order. Then $P(G\times C_{2})$ has a perfect
matching.

###### Proof.

$G\times C_{2}$ has a unique involution. ∎

###  4.4 $2$-groups

The following theorem characterises the $2$-groups having perfect matchings in
their power graphs.

######  Theorem 4.8.

Let $G$ be a finite group with $|G|=2^{n}$. Then $P(G)$ has a perfect matching
if and only if $G$ is cyclic or generalized quaternion.

###### Proof.

We have $|O(G)|=|O(G_{G}(S))|=1$, so Theorems 3.1 and 3.2 show that $G$ has a
perfect matching if and only if it has a unique involution. The $2$-groups
with unique involution are the cyclic and generalized quaternion groups. ∎

##  5 A number-theoretic result

The functions $\tau(n)$ (the number of divisors of $n$) and $\phi(n)$ (Euler’s
totient function) are two of the best-studied in number theory. The result we
require about them is elementary, but we have not found a proof in the
literature.

######  Theorem 5.1.

Let $n$ be a positive integer. If $n\geq 30$, then $\tau(n)<\phi(n)$.

The proof depends on the formulae for these functions: if
$n=\displaystyle{\prod_{i=1}^{r}p_{i}^{a_{i}}}$, where $p_{1},\ldots,p_{r}$
are distinct primes and $a_{1},\ldots,a_{r}$ are positive integers, then

  1. (a)

$\tau(n)=\displaystyle{\prod_{i=1}^{r}(a_{i}+1)}$,

  2. (b)

$\phi(n)=\displaystyle{\prod_{i=1}^{r}p_{i}^{a_{i}-1}(p_{i}-1)}$.

We use the following technical lemma:

######  Lemma 5.2.

Let $p$ be a prime, and $a$ a positive integer.

  1. (a)

If $(p,a)\notin\\{(2,1),(2,2)\\}$, then $p^{a-1}(p-1)\geq a+1$, with equality
only if $(p,a)\in\\{(2,3),(3,1)\\}$.

  2. (b)

If $p\neq 2$ and $(p,a)\neq(3,1)$, then $p^{a-1}(p-1)\geq 2(a+1)$, with
equality only if $(p,a)=(5,1)$.

###### Proof.

The function $f(x)=p^{x-1}(p-1)-(x+1)$ has derivative
$f^{\prime}(x)=p^{x-1}(p-1)\log p-1$, which is positive for $x\geq 1$ if
$p\neq 2$, and for $x\geq 2$ if $p=2$. So for each $p$ we only have to check
the smallest values of $x$. ∎

#### Proof of the theorem

To prove the theorem, we see that if $n$ is odd or divisible by $8$, then
$\phi(n)\geq\tau(n)$, with strict inequality if the factorization includes
$2^{4}$, $3^{2}$, or a prime larger than $3$. If $n$ is exactly divisible by
$2^{a}$ with $a=1$ or $a=2$, then $2^{a-1}(2-1)\geq\frac{1}{2}(a+1)$, and so
as long as we have a factor $3^{3}$, $5^{2}$ or a prime greater than $5$ the
strict inequality holds. The cases $n=20$ and $n=36$ satisfy the conclusion.
Thus, the only cases for which it fails are $1,2,3,4,6,8,10,12,18,24,30$.

The result we actually require is the following corollary of this theorem. The
_independence number_ $\alpha(\Gamma)$ of a graph $\Gamma$ is the size of the
largest set of vertices containing no edges.

######  Corollary 5.3.

Let $n$ be a positive integer. If $n\notin\\{2,6\\}$, then the independence
number of the power graph of the cyclic group $C_{n}$ is strictly less than
$\phi(n)$.

###### Proof.

In a cyclic group $C_{n}$, if two elements have the same order, then each is a
power of the other, so they are joined in the power graph. So an independent
set in the power graph has at most one element of each possible order, and its
cardinality is at most $\tau(n)$. By Theorem 5.1, the conclusion holds if
$n>30$; it is easily checked directly for smaller values of $n$. ∎

######  Remark 5.4.

In fact, it is easy to see that the independence number of $P(C_{n})$ is the
size of the largest antichain in the lattice of divisors of $n$. If $n$ is a
product of $m$ primes (not necessarily distinct), then an antichain of maximum
size is obtained by taking all distinct products of $\lfloor m/2\rfloor$
primes, or all distinct products of $\lceil m/2\rceil$ primes. (This extension
of the celebrated Sperner lemma was proved by de Bruijn _et al._ [3].) This
fact can be used to simplify the calculations in the Corollary.

##  6 The matching number of the enhanced power graph

Recall that the _enhanced power graph_ $P_{e}(G)$ of a finite group $G$ is the
graph with vertex set $G$ in which two vertices $x$ and $y$ are joined if
there exists $z$ such that both $x$ and $y$ are powers of $z$ (in other words,
if $\langle x,y\rangle$ is cyclic). So the enhanced power graph contains the
power graph as a spanning subgraph, and its matching number is at least as
great as that of the power graph.

From our earlier work, there are several cases where equality holds:

  1. (a)

If $|G|$ is odd, then the power graph has a matching covering all but one
vertex; the same is true of the enhanced power graph.

  2. (b)

If the power graph of $G$ has a perfect matching, then so does the enhanced
power graph.

  3. (c)

Examining the proof of the formula for the matching number of the power graph
of a nilpotent group (Theorem b), we see that the same formula holds for the
enhanced power graph.

In fact, we are going to prove that the matching numbers are always equal,
even in cases where we cannot compute them:

######  Theorem 6.1.

Let $G$ be a finite group. Then the matching numbers of the power graph and
the enhanced power graph of $G$ are equal.

###### Proof.

Let $G$ be any finite group. Choose a matching $M$ of maximum size in the
enhanced power graph. If all its edges belong to the power graph, there is
nothing to prove. Otherwise, we are going to change $M$ to $M^{\prime}$ so
that $M^{\prime}$ is a matching of the same size and has one fewer edge which
doesn’t belong to the power graph.

So let $\\{g,h\\}$ be an edge of the matching $M$ which belongs to the
enhanced power graph but not to the power graph. Choose this edge so that
$\mathop{\mathrm{lcm}}(o(g),o(h))$ is as large as possible. Let $l$ be this
lcm. Then $\langle g,h\rangle=C$ is a cyclic group of order $l$. Let
$x_{1},\ldots,x_{\phi(l)}$ be the generators of $C$. They are joined to all
vertices in $C$ in the power graph.

Assume first that least one of $x_{1},\ldots,x_{\phi(l)}$, say $x_{i}$, is not
covered by the edges of $M$. Then we can replace the edge $\\{g,h\\}$ by the
edge $\\{g,x_{i}\\}$, which is an edge of the power graph.

So we can assume that all of $x_{1},\ldots,x_{\phi(l)}$ are covered by edges
in $M$. Let $\\{x_{i},y_{i}\\}$ be an edge of $M$ for $i=1,\ldots,\phi(l)$.

For each $i$, there are three cases:

  1. (a)

$x_{i}$ is a power of $y_{i}$;

  2. (b)

$y_{i}$ is a power of $x_{i}$;

  3. (c)

neither of the above.

In case (a), $g$ and $h$ are powers of $x_{i}$, and hence also powers of
$y_{i}$. So we can replace the edges $\\{g,h\\}$ and $\\{x_{i},y_{i}\\}$ by
$\\{g,x_{i}\\}$ and $\\{h,y_{i}\\}$, both of which are edges of the power
graph.

In case (c), $\\{x_{i},y_{i}\\}$ is an edge of the enhanced power graph but
not of the power graph, and $\mathop{\mathrm{lcm}}(o(x_{i}),o(y_{i}))>l$,
contradicting the choice of the edge $\\{g,h\\}$.

So we must be in case (b) for all $i$. This means that all of
$y_{1},\ldots,y_{\phi(l)}$ belong to $C$.

Now suppose that $l\notin\\{2,6\\}$. Then the independence number of the power
graph of $C$ is strictly smaller than $\phi(l)$; so the set
$\\{y_{1},\ldots,y_{\phi(l)}\\}$ is not an independent set in the power graph,
and so it contains at least one edge, say $\\{y_{i},y_{j}\\}$. In this case,
we replace the three edges $\\{g,h\\}$, $\\{x_{i},y_{i}\\}$,
$\\{x_{j},y_{j}\\}$ by $\\{g,x_{i}\\}$, $\\{h,x_{j}\\}$, $\\{y_{i},y_{j}\\}$,
all edges of the power graph.

Finally, the case $l=2$ is clearly impossible. If $l=6$, let $C=\langle
z\rangle$ be the cyclic group of order $6$. There are just two nonedges of the
power graph, namely $\\{z^{3},z^{2}\\}$ and $\\{z^{3},z^{4}\\}$; without loss
of generality, $\\{g,h\\}=\\{z^{2},z^{3}\\}$. We have
$\\{x_{1},x_{2}\\}=\\{z,z^{5}\\}$. Hence necessarily
$\\{y_{1},y_{2}\\}=\\{1,z^{4}\\}$. But this is an edge of the power graph, so
the argument in the preceding paragraph applies. ∎

##  7 Conclusion and open problems

The most important problem we have been unable to solve is the following.

######  Problem 1.

  1. (a)

Find the matching number of $P(G)$ for any finite group $G$.

  2. (b)

Find a necessary and sufficient condition for a group $G$ to have a perfect
matching.

The preceding section gives an interesting light on the relation between the
power graph and the enhanced power graph. We mention the following known
result. A finite group is an _EPPO group_ (for Elements of Prime Power Order
if every element has prime power order. The _Gruenberg–Kegel graph_ (or _prime
graph_) of a group $G$ has vertex set the set of prime divisors of $|G|$, with
an edge from $p$ to $q$ if and only if $G$ contains an element of order $pq$.

######  Theorem 7.1.

The following conditions on a finite group $G$ are equivalent:

  1. (a)

$P(G)=P_{e}(G)$;

  2. (b)

$G$ is an EPPO group;

  3. (c)

the Gruenberg–Kegel graph of $G$ is null.

The study of groups satisfying this condition was begun by Higman [9] in 1957,
and all simple EPPO groups were found by Suzuki [16] in 1962; the complete
determination of these groups was given by Bannuscher and Tiedt in 1994 [2].

The following problem comprises a generalization of this theorem.

######  Problem 2.

Let $p$ be a monotone graph parameter (that is, if $\Gamma$ is a spanning
subgraph of $\Delta$ then $p(\Gamma)\leq p(\Delta)$). Determine the finite
groups for which $p(P(G))=p(P_{e}(G))$.

Theorem 6.1 shows that, if $p$ is the matching number, then the solution is
“all finite groups”. Also, it is easy to show that, if $p$ is the clique
number, then the solution is “all groups where the largest order of an element
is a prime power”.

## Acknowledgments

The author Swathi V V acknowledges the support of Council of Scientific and
Industrial Research, India (CSIR) (Grant No-09/874(0029)/2018-EMR-I), and DST,
Government of India,‘FIST’ (No.SR/FST /MS-I/2019/40).

The collaboration of the authors was made possible by the Research Discussion
on Graphs and Groups (RDGG) at CUSAT, Kochi, India, organised by Vijayakumar
Ambat and Aparna Lakshmanan S. We are grateful to them for this opportunity,

## References

  * [1] László Babai and Peter J. Cameron, Automorphisms and enumeration of switching classes of tournaments, Electronic J. Combinatorics 7(1) (2000), article #R38.
  * [2] W. Bannuscher and G. Tiedt, On a theorem of Deaconescu, Rostock. Math. Kolloq. 47 (1994), 23–26.
  * [3] N. G. de Bruijn, Ca. van Ebbenhorst Tengbergen, and D. Kruyswijk, On the set of divisors of a number, Nieuw Arch. Wiskunde (2) 23 (1951), 191–193.
  * [4] Peter J. Cameron. The power graph of finite group II. Journal of Group Theory, 13(6):779–783, 2010.
  * [5] Peter J Cameron and Shamik Ghosh. The power graph of a finite group. Discrete Mathematics, 311(13):1220–1222, 2011.
  * [6] Ivy Chakrabarty, Shamik Ghosh, and MK Sen. Undirected power graphs of semigroups Semigroup Forum, 78:410–426, 2009.
  * [7] Brian Curtin and Gholam Reza Pourgholi. Edge-maximality of power graphs of finite cyclic groups. Journal of Algebraic Combinatorics, 40(2):313–330, 2014.
  * [8] Brian Curtin and Gholam Reza Pourgholi. An euler totient sum inequality. Journal of Number Theory, 163:101–113, 2016.
  * [9] Graham Higman, Finite groups in which every element has prime power order, J. London Math. Soc. (1) 32 (1957), 335–342.
  * [10] A. V. Kelarev and S. J. Quinn. A combinatorial property and power graphs of groups. Contributions to general algebra, 12(58):3–6, 2000.
  * [11] Xuanlong Ma and Min Feng. On the chromatic number of the power graph of a finite group. Indagationes Mathematicae, 26(4):626–633, 2015.
  * [12] Xuanlong Ma, Ruiqin Fu, and Xuefei Lu. On the independence number of the power graph of a finite group. Indagationes Mathematicae, 29(2):794–806, 2018.
  * [13] M. Mirzargar, A. R. Ashrafi, and M. J. Nadjafi-Arani. On the power graph of a finite group. Filomat, 26(6):1201–1208, 2012.
  * [14] G. R. Pourgholi, H. Yousefi-Azari, and A. R. Ashrafi. The undirected power graph of a finite group. Bulletin of the Malaysian Mathematical Sciences Society, 38(4):1517–1525, 2015.
  * [15] D. J. S. Robinson, A Course in the Theory of Groups, Berlin, New York: Springer-Verlag, 1996.
  * [16] M. Suzuki, On a class of doubly transitive groups, Ann. Math. 75 (1962), 105–145.
  * [17] W. T. Tutte, The factorization of linear graphs, Journal of the London Mathematical Society, 22:107–111, 1947.