%``````````````````% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P3.16}{24(3)}{2017} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf On the structure of the power graph and \\ the enhanced power graph of a group} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Ghodratollah Aalipour\\ \small School of Mathematical Science\\[-0.8ex] \small Rochester Institute of Technology (RIT)\\[-0.8ex] \small Rochester, NY 14623, USA.\\ \small\tt alipour.ghodratollah@gmail.com\\ \and Saieed Akbari \\ \small Department of Mathematical Sciences\\[-0.8ex] \small Sharif University of Technology \\[-0.8ex] \small Tehran, Iran.\\ \small\tt s\_akbari@sharif.edu\\ \and Peter J. Cameron\\ \small School of Mathematics and Statistics\\[-0.8ex] \small University of St Andrews\\[-0.8ex] \small St Andrews, Fife KY16 9SS, UK.\\ \small\tt pjc20@st{\rm-}andrews.ac.uk \and Reza Nikandish \\ \small Department of Basic Sciences\\[-0.8ex] \small Jundi-Shapur University of Technology \\[-0.8ex] \small Dezful, Iran.\\ \small\tt r.nikandish@ipm.ir \and Farzad Shaveisi\\ \small Department of Mathematics, Faculty of Science\\[-0.8ex] \small Razi University \\[-0.8ex] \small Kermanshah, Iran.\\ \small\tt f.shaveisi@razi.ac.ir } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Sep 28, 2016}{Jul 17, 2017}{Jul 28, 2017}\\ \small Mathematics Subject Classifications: 05C25, 05C69, 20D60} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} Let $G$ be a group. The \emph{power graph} of $G$ is a graph with the vertex set $G$, having an edge between two elements whenever one is a power of the other. We characterize nilpotent groups whose power graphs have finite independence number. For a bounded exponent group, we prove its power graph is a perfect graph and we determine its clique/chromatic number. Furthermore, it is proved that for every group $G$, the clique number of the power graph of $G$ is at most countably infinite. We also measure how close the power graph is to the \emph{commuting graph} by introducing a new graph which lies in between. We call this new graph the \emph{enhanced power graph}. For an arbitrary pair of these three graphs we characterize finite groups for which this pair of graphs are equal. % keywords are optional \bigskip\noindent \textbf{Keywords:} power graph, clique number, chromatic number, independence number, group. \end{abstract} \section{Introduction} We begin with some standard definitions from graph theory and group theory. Let $G$ be a graph with vertex set $V(G)$. If $x\in V(G)$, then the number of vertices adjacent to $x$ is called the \textit{degree} of $x$, and denoted by $\deg(x)$. %A \textit{Hamilton path} is a path in an undirected graph which meets each vertex exactly once. The \textit{distance} between two vertices in a graph is the number of edges in a shortest path connecting them. The \textit{diameter} of a connected graph $G$, denoted by ${\rm diam} (G)$, is the maximum distance between any pair of vertices of $G$. If $G$ is disconnected, then ${\rm diam} (G)$ is defined to be infinite. A \textit{star} is a graph in which there is a vertex adjacent to all other vertices, with no further edges. The \textit{center} of a star is a vertex that is adjacent to all other vertices. Let $U\subseteq V(G)$. The induced subgraph on $U$ is denoted by $\langle U\rangle$. An \textit{independent set} is a set of vertices in a graph, no two of which are adjacent; that is, a set whose induced subgraph is null. The {\it{independence number}} of a graph $G$ is the cardinality of the largest independent set and is denoted by $\alpha(G)$. A subset $S$ of the vertex set of $G$ is called a \textit{dominating set} if for every vertex $v$ of $G$, either $v\in S$ or $v$ is adjacent to a vertex in $S$. The minimum size of dominating sets of $G$, denoted by $\gamma(G)$, is called the \textit{domination number} of $G$. A \textit{clique} in a graph is a set of pairwise adjacent vertices. The supremum of the sizes of cliques in $G$, denoted by $\omega(G)$, is called the \textit{clique number} of $G$. By $\chi(G)$, we mean the \textit{chromatic number} of $G$, i.e., the minimum number of colours which can be assigned to the vertices of $G$ in such a way that every two adjacent vertices have different colours. The cyclic group of order $n$ is denoted by $C_n$. A group $G$ is called \textit{periodic} if every element of $G$ has finite order. For every element $g\in G$, the order of $g$ is denoted by $o(g)$. If there exists an integer $n$ such that for all $g\in G$, $g^n=e$, where $e$ is the identity element of $G$, then $G$ is said to be of \textit{bounded exponent}. If $G$ is of bounded exponent, then the \textit{exponent} of $G$ is the least common multiple of the orders of its elements; that is, the least $n$ for which $g^n=e$ for all $g\in G$. A group $G$ is said to be \textit{torsion-free} if apart from the identity every element of $G$ has infinite order. Let $p$ be a prime number. The \textit{$p$-quasicyclic group} (known also as the \textit{Pr\"{u}fer group}) is the $p$-primary component of $\mathbb{Q}/\mathbb{Z}$, that is, the unique maximal $p$-subgroup of $\mathbb{Q}/\mathbb{Z}$. It is denoted by $ C_{p^\infty}$. The \textit{center} of a group $G$, denoted by $Z(G)$, is the set of elements that commute with every element of $G$. A group $G$ is called \textit{locally finite} if every finitely generated subgroup of $G$ is finite. A group is \textit{locally cyclic} if any finitely generated subgroup is cyclic. Other concepts will be defined when needed. Now, we define the object of interest to us in this paper. Let $G$ be a group. The \textit{power graph} of $G$, denoted by $\mathcal{G}(G)$, is the graph whose vertex set is $G$, two elements being adjacent if one is a power of the other. The concept of a power graph was first introduced by Kelarev and Quinn~\cite{kq}. Note that in \cite{kq}, a power graph is directed. The full automorphism group of a power graph of a finite group was characterized in \cite{feng-xuanlong-wang}. Also, see \cite{akc} for a survey of results and open questions on power graphs. Other studies include \cite{ghosh} for semigroups and \cite{cameronghosh,cameron} for groups. In the last of these papers, it was shown that, for a finite group, the undirected power graph determines the directed power graph up to isomorphism. As a consequence, two finite groups which have isomorphic undirected power graphs have the same number of elements of each order. Our results about the power graph fall into four classes. \begin{itemize}\itemsep0pt \item In Section~\ref{independence}, we consider the independence number $\alpha(\mathcal{G}(G))$. We show that if the independence number is finite then $G$ is a locally finite group whose centre has finite index. Using this we are able to give precise characterizations of nilpotent groups $G$ for which $\alpha(\mathcal{G}(G))$ is finite -- such a group (if infinite) is the direct product of a $p$-quasicyclic group and a nilpotent $p'$-group. \item In Section~\ref{colouring}, we show that the power graph of every group has clique number at most countable. We note here that Shitov~\cite{shitov} answered a question in an earlier version of this paper by showing that the chromatic number of the power graph of every group is also at most countable. \item A group with finite clique number must be of bounded exponent. Hence we obtain a structure theorem for abelian groups with this property, as well as showing that it passes to subgroups and supergroups of finite index. \item We show that, if $G$ has bounded exponent, then $\mathcal{G}(G)$ is perfect. \item Finally, in Section~\ref{misc} there are some miscellaneous results. A group is periodic if and only if its power graph is connected, and in this case its diameter must be at most $2$. Also we show that, if all vertex degrees in $\mathcal{G}(G)$ are finite, then $G$ is finite. \end{itemize} In the recent paper \cite{feng-xuanlong-wang}, the authors prove that the power graph of every finite group is perfect. We acknowledge that our result on the perfectness along with all results in the Section \ref{sec-power-graph} were proved independently in 2011. Another well-studied graph associated to a group $G$ is the \emph{commuting graph} of $G$. This graph appears to be first studied by Brauer and Fowler in 1955 in \cite{Brauer-Fowler} as a part of classification of finite simple groups. As the elements of the centre are adjacent to all other vertices, usually the vertices are assumed to be non-central. For more information on the commuting graph, see \cite{Araujo-et, Giudici-Pope, Woodcock} and the references therein. In Section \ref{power-commuting} we relate the power graph to the commuting graph and characterize when they are equal for finite groups. A new graph pops up while considering these graphs, a graph whose vertex set consists of all group elements, in which two vertices $x$ and $y$ are adjacent if they generate a cyclic group. We call this graph as the \emph{enhanced power graph} of $G$ and we denote it by $\mathcal{G}_e(G)$. The enhanced power graph contains the power graph and is a subgraph of the commuting graph. We further study some properties of this graph in the Section \ref{power-commuting}. %The enhanced power graph lies between the power graph and the commuting graph. We characterize the finite groups for which equality holds for any two of these three graphs, and the solvable groups for which the power graph is equal to the commuting graph. Other results are as follows: \begin{itemize}\itemsep0pt \item If the power graphs of $G$ and $H$ are isomorphic, then their enhanced power graphs are isomorphic. \item A maximal clique in the enhanced power graph is either a cyclic or a locally cyclic subgroup. \item $\mathcal{G}_e(G)$ has finite clique number if and only if $G$ has finite exponent; if this holds, then the clique number of $\mathcal{G}_e(G)$ is equal to the largest order of an element of $G$. Also, for any group $G$, the clique number of $\mathcal{G}_e(G)$ is at most countable. \end{itemize} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Power graphs of groups}\label{sec-power-graph} \subsection{Independent sets in power graphs}\label{independence} In this section we provide some results on the finiteness of the independence number of the power graphs. In the proof of the our first theorem, we need the following definition. Let $G$ be a group and associate with $G$ a graph $\Gamma(G)$ as follows: the vertices of $\Gamma(G)$ are the elements of $G$ and two vertices $g$ and $h$ of $\Gamma(G)$ are joined by an edge if and only if $g$ and $h$ do not commute, see \cite{akbari} and \cite{neuman} for more details. Now, we have the following result. \begin{theorem}\label{finiteindependent} Let $G$ be a group and $\alpha({\mathcal {G}}(G))<\infty$. Then \begin{enumerate} \item[\rm (i)] $[G:Z(G)]<\infty$. \item[\rm (ii)] $G$ is locally finite. \end{enumerate} \end{theorem} \begin{proof} {(i) First we note that if $x$ and $y$ are adjacent in $\Gamma(G)$, then $x$ and $y$ are not adjacent in $\mathcal{G}(G)$. Thus $\omega(\Gamma(G))\leq\alpha({\mathcal {G}}(G))<\infty$. Hence \cite[Theorem 6]{neuman} implies that $[G:Z(G)]<\infty$.\\ (ii) Let $H$ be a finitely generated subgroup of $G$. Then by (i) and \cite[1.6.11]{robinson}, $Z(H)$ is finitely generated, too. So by the fundamental theorem for finitely generated abelian groups we find that $Z(H)\cong \mathbb{Z}^n\times C_{q_1}\times\cdots \times C_{q_k}$, where $n$ and $k$ are non-negative integers and every $q_i$, $1\leq i\leq k$, is a power of a prime number. Since $\alpha({\mathcal {G}}(\mathbb{Z}))=\infty$, we deduce that $H$ is a finite group and so the proof is complete.} \end{proof} Now, we characterize those abelian groups whose power graphs have finite independence number. First we need the following theorem. \begin{theorem}{\rm(\cite[4.3.11]{robinson})}\label{rob4.3.11} If $G$ is an abelian group which is not torsion-free, then it has a non-trivial direct summand which is either cyclic or quasicyclic. \end{theorem} \begin{theorem}\label{alphafinite} Let $G$ be an abelian group such that $\alpha(\mathcal{G}(G))<\infty$. Then either $G$ is finite or $G\cong C_{p^\infty}\times H$, where $H$ is a finite group and $p\nmid |H|$. \end{theorem} \begin{proof} {If $G$ is torsion-free, then $G$ contains $\mathbb{Z}$ and so $\alpha(\mathcal{G}(G))\geq\alpha(\mathcal{G}({\mathbb{Z}}))=\infty$, a contradiction. Thus by Theorem \ref{rob4.3.11}, $G=G_1\oplus H_1$, where $G_1$ is either cyclic or quasicyclic. If $H_1$ is trivial, then we are done. Otherwise, $\alpha(\mathcal{G}(H_1))<\infty$ implies that $H_1=G_2\oplus H_2$, where $G_2$ is either cyclic or quasicyclic. So $G=G_1\oplus G_2\oplus H_2$. By repeating this procedure and using $\alpha(\mathcal{G}(G))<\infty$, we deduce that there exists a positive integer $n$ such that $G\cong \bigoplus_{i=1}^n G_i$, where every $G_i$ is either cyclic or quasicyclic. We show that at most one $G_i$ is quasicyclic. By the contrary, suppose that $G$ contains the group $ C_{p^\infty}\times C_{q^\infty}$. It is not hard to see that for every positive integer $n$, $I_n=\{(1/p^i+\mathbb{Z},1/q^{n-i+1}+\mathbb{Z})\,:\, 1\leq i \leq n\}$ is an independent set of size $n$, a contradiction. So either $G\cong C_{p^\infty}\times \prod_{i=1}^n C_{p_i^{\alpha_i}}$ or $G\cong\prod_{i=1}^n C_{p_i^{\alpha_i}}$, where $p$ and $p_i$ are prime numbers. Now, suppose that the first case occurs. To complete the proof, we show that $p\neq p_i$, for every $i$, $1\leq i\leq n$. By contrary, suppose that $p=p_i$, for some $i$. Then $ C_{p^\infty}\times C_{p}$ is a subgroup of $G$. Since $ C_{p^\infty}\times\{1\}$ is an independent set in $\mathcal{G}( C_{p^\infty}\times C_{p})$, we get a contradiction. So, the proof is complete.} \end{proof} \begin{theorem}\label{alphapgroup} Let $p$ be a prime number and $G$ be a $p$-group such that $\alpha(\mathcal{G}(G))<\infty$. Then either $G$ is finite or $G\cong C_{p^\infty}$. \end{theorem} \begin{proof} {Since $\alpha(\mathcal{G}(G))<\infty$, we deduce that $\alpha(\mathcal{G}(Z(G)))<\infty$. Thus by Theorem \ref{alphafinite}, either $Z(G)$ is finite or $Z(G)\cong C_{p^\infty}$, for some prime number $p$. If $Z(G)$ is finite, then by Theorem \ref{finiteindependent}, $G$ is finite. Now, suppose that $Z(G)\cong C_{p^\infty}$. To complete the proof, we show that $G$ is abelian. To the contrary, suppose that there exists $a\in G\setminus Z(G)$. Let $H=\langle Z(G)\cup\{a\}\rangle$. Clearly, $H$ is an abelian $p$-subgroup of $G$ and $\alpha(\mathcal{G}(H))<\infty$. So, by Theorem \ref{alphafinite}, $H\cong C_{p^\infty}\cong Z(G)$. Since every proper subgroup of $ C_{p^\infty}$ is finite, we get a contradiction. Hence $G$ is abelian and $G=Z(G)\cong C_{p^\infty}$.} \end{proof} Now, we exploit Theorem \ref{alphapgroup} to extend Theorem \ref{alphafinite} to nilpotent groups. \begin{remark}\label{decomposition} Let $H$ and $K$ be two subgroups of $G$. If $H\cap K=\{e\}$, $G=HK$ and $H\subseteq Z(G)$, then $G\cong H\times K.$ \end{remark} \begin{theorem}\label{nilpotentalpha} Let $G$ be an infinite nilpotent group. Then $\alpha(\mathcal{G}(G))<\infty$ if and only if $G\cong C_{p^\infty}\times H$, for some prime number $p$, where $H$ is a finite group and $p\nmid |H|$. \end{theorem} \begin{proof} {First suppose that $G\cong C_{p^\infty}\times H$, where $H$ is a finite group and $p\nmid |H|$. Suppose to the contrary, $\{(s_n/p^{\alpha_n}+\mathbb{Z},g_n)\,:\, n\geq 1, s_n\in\mathbb{Z}, p\nmid s_n\,{\rm and}\,g_n\in H \}$ is an infinite independent set of $\mathcal{G}(G)$. Since $H$ is a finite group, there exists $g\in H$ such that the infinite set $$\{(s_n/p^{\alpha_n}+\mathbb{Z},g)\,:\, n\geq 1, s_n\in\mathbb{Z}\ {\rm and}\ p\nmid s_n \}$$ forms an independent set. Since $o(g)<\infty$, there exist $\alpha_i$ and $\alpha_j$ such that $p^{\alpha_i}\equiv p^{\alpha_j}({\rm mod }\, o(g))$ and $\alpha_i>\alpha_j$. On the other hand, we know that $\gcd(s_i,p)=1$. So, let $t_i$ be the multiplicative inverse of $s_i$ in $ C_{p^{\alpha_j}}$. Thus by Chinese Reminder Theorem, there exists a positive integer $x$ such that $x\equiv t_is_j({\rm mod}\, p^{\alpha_j})$ and $x\equiv p^{\alpha_j-\alpha_i}({\rm mod}\,o(g))$. Therefore, we have $$p^{\alpha_i-\alpha_j}x\frac{s_i}{p^{\alpha_i}}-\frac{s_j}{p^{\alpha_j}}=\frac{s_ix-s_j}{p^{\alpha_j}}\in \mathbb{Z},\hspace{.5cm} g^{xp^{\alpha_i-\alpha_j}}=g.$$ Thus, $(s_i/p^{\alpha_i}+\mathbb{Z},g)$ and $(s_j/p^{\alpha_j}+\mathbb{Z},g)$ are adjacent, a contradiction. Conversely, suppose that $\alpha(\mathcal{G}(G))<\infty$. Then by Theorem \ref{finiteindependent}, $[G:Z(G)]<\infty$ and so $G=Z(G)H$, where $H$ is a finitely generated subgroup of $G$. Now, Theorem \ref{finiteindependent} implies that $H$ is finite. By Theorem \ref{alphafinite}, $Z(G)=AB$, where $A\cong C_{p^\infty}$ and $B$ is a finite group such that $p\nmid |B|$. Also, since $H$ is nilpotent, we have $H\cong H_pH_{p_1}\cdots H_{p_t}$, where $H_p$ and $H_{p_i}$ ($1\leq i\leq t$) are sylow $p$-subgroup and sylow $p_i$-subgroup of $H$, respectively. We show that $H_p\subseteq A$. To the contrary, suppose that $x\in H_p\setminus A$. Then $\langle A,x\rangle$ is a $p$-group and so by Theorem \ref{alphapgroup}, $\langle A,x\rangle\cong C_{p^\infty}\cong \langle A\rangle$. Since every proper subgroup of $ C_{p^\infty}$ is finite, we get a contradiction. Thus $H_p\subseteq Z(G)$ and so $G=ABH_{p_1}\cdots H_{p_t}$. Since $G$ is nilpotent, $BH_{p_1}\cdots H_{p_t}$ is a finite subgroup of $G$ and $p\nmid |BH_{p_1}\cdots H_{p_t}|$. Hence by Remark \ref{decomposition}, $G\cong A\times BH_{p_1}\cdots H_{p_t}$, as desired.~} \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{The colouring of power graphs}\label{colouring} Let $G$ be a group. In this section, we first show that the chromatic number of the power graph of $G$ is finite if and only if the clique number of the power graph of $G$ is finite and this statement is also equivalent to that the exponent of $G$ is finite. Then it is proved that the clique number of the power graph of $G$ is at most countable. Finally, it is shown that the power graph of every bounded exponent group is perfect. \begin{lemma}\label{chrombond} Let $G$ be a group. If $\omega(\mathcal{G}(G))$ is finite, then $G$ is of bounded exponent. \end{lemma} \begin{proof} {By the contrary, suppose that $G$ is not of bounded exponent. Then for every positive integer $k$, there is an element $g_k\in G$ such that $o(g_k)>2^k$. So one can easily show that $\{g_k^{2^i}\,|\,0\leq i\leq k\}$ is a clique of size $k+1$ in ${\mathcal {G}}(G)$. This implies that $\omega({\mathcal {G}}(G))=\infty$, a contradiction. The proof is complete. } \end{proof} \begin{remark} The proof uses the Axiom of Choice for families of finite sets. \end{remark} \begin{corollary} Let $G$ be an abelian group and $\omega({\mathcal{G}}(G))<\infty$. Then there are some positive integers $r$ and $n_i$ and sets $I_i$, $1\leq i\leq r$ such that $$G\cong \prod_{i=1}^r\prod _{I_i} C_{n_i}.$$ \end{corollary} \begin{proof} {Since $\omega({\mathcal{G}}(G))<\infty$, by Lemma \ref{chrombond}, $G$ is bounded exponent. So the assertion follows from Pr\"{u}fer-Baer Theorem (see \cite[4.3.5]{robinson}).} \end{proof} \begin{theorem}\label{conuntclique} The clique number of the power graph of any group is at most countably infinite. \end{theorem} \begin{proof} {Let $C$ be a clique in the power graph of $G$, and take $x\in C$. Then the remaining vertices $y$ of $C$ are of two types: \begin{itemize} \item $y=x^n$ for some $n$; \item $x=y^n$ for some $n$. \end{itemize} Clearly, there are at most countably many of the first type. We denote the set of vertices of the second type by $C(n)$. We show that $C(n)$ is at most countably infinite. If there is only one $y$ in $C(n)$, then there is nothing to prove; so suppose there are at least two elements in $C(n)$. We claim that every element in $C(n)$ has finite order. Choose $y,y'\in C(n)$. With no loss of generality, one can assume that $y'=y^k$, for some positive integer $k$. So $y^{(k-1)n}=1$. This implies that the orders of both $y$ and $y'$ are finite. Thus the claim is proved. Now, for every positive integer $k$, define $C(n,k)=\{y\in C(n)\,|\,o(y)=k\}$. By the claim, $C(n)=\bigcup_{k\geq1}C(n,k)$. It is not hard to show that for every $a,b\in C(n,k)$, $\langle a\rangle=\langle b\rangle$ and so $C(n,k)$ is finite. Therefore, $C(n)$ is at most countably infinite.} \end{proof} In an earlier version of this paper (on the arXiv), we asked whether it is the case that the chromatic number of the power graph of any group is at most countable. We proved that this was the case for several classes of groups (abelian groups, periodic groups and free groups). In the meantime, Shitov~\cite{shitov}, acknowledging our paper, has proved that the answer to our question is affirmative, more generally for all power-associative magmas. \subsubsection{Perfectness of the power graph}\label{perfectness} A graph $G$ is called \textit{perfect} if for every finite induced subgraph $H$ of $G$, $\chi(H)=\omega(H)$. The Strong Perfect Graph Theorem states that a finite graph $G$ is perfect if and only if neither $G$ nor $\overline{G}$ (the complement of $G$) contains an induced odd cycle of length at least $5$, see \cite[Theorem 14.18]{bondy}. However, this is a deep theorem, and we do not need it to prove our results. Utilizing Lemma \ref{chrombond} to colour the power graph with a finite set of colours we require the group to be bounded exponent. Here we show that for such groups the resulting power graph is always perfect and can be finitely coloured. To prove this result we facilitate the concepts of comparability graph. Let $\leq$ be a binary relation on the elements of a set $P$. If $\leq$ is reflexive and transitive, then $(P,\leq)$ is called a \textit{pre-ordered set}. All partially ordered sets are pre-ordered. The {\it comparability graph} of a pre-ordered set $(P,\leq)$ is the simple graph $\Upsilon(P)$ with the vertex set $P$ and two distinct vertices $x$ and $y$ are adjacent if and only if either $x\leq y$ or $y\leq x$ (or both). \begin{theorem}\label{comparabilitygraph} Let $m$ be a positive integer and $P$ be a pre-ordered set {\rm (}not necessarily finite{\rm)} whose maximum chain size is $m$. Then the comparability graph $\Upsilon(P)$ is perfect and $$\omega(\Upsilon(P))=\chi(\Upsilon(P))=m.$$ \end{theorem} \begin{proof} {The result is well known for comparability graphs of partial orders; our proof is a slight extension of this. Since the class of comparability graphs is closed under taking induced subgraphs, it is enough to prove that the comparability graph of $P$ has equal clique number and chromatic number. Clearly, a clique in a $\Upsilon(P)$ is a chain in $P$, while a colouring is a partition into antichains. First we show that $\omega(\Upsilon(P))=m$. Let $C$ be a clique in $\Upsilon(P)$. Then $C$ is a chain in $P$, and so $|C|\leq m$. Thus $\omega(\Upsilon(P))=m$. Now, we show that $\chi(\Upsilon(P))\leq m$. We form a directed graph by putting an arc from $x$ to $y$ whenever $x\le y$ but $y\not\le x$; and, if $C$ is an equivalence class of the relation $\equiv$ defined by $x\equiv y$ if $x\le y$ and $y\le x$, then take an arbitrary directed path on the elements of $C$. Clearly, the longest directed path contains $m$ vertices. Let $P_i$ be the set of elements $x$ for which the longest directed path ending at $x$ contains $i$ vertices. It is easy to see that $P_i$ is an independent set; these sets partition $P$ into $m$ classes.} \end{proof} Now, we show that the power graph of a group is the comparability graph of a pre-ordered set. First, we define some notations. Let $n$ be a positive integer and $\mathcal{D}(n)$ be the set of all divisors of $n$ in $\mathbb{N}$. Define a relation $\preceq$ on $\mathcal{D}(n)$ by $r\preceq s$ if and only if $r\mid s$. Clearly, $(\mathcal{D}(n),\preceq)$ is a partially ordered set. Denote the set of all chains of $(\mathcal{D}(n),\preceq)$ by ${\mathcal{C}}(n)$. Using this convention we are able to determine the clique/chromatic number of the power graph of a group of bounded exponent (see Lemma \ref{chrombond}). \begin{theorem}\label{main-theorem} Let $G$ be a group of exponent $n$. Then $\mathcal{G}(G)$ is a perfect graph and $$\chi(\mathcal{G}(G))=\omega(\mathcal{G}(G))=\max\Bigg\{\sum\limits_{\substack{d\in C\\ G_d\neq \emptyset}}\phi(d)\,:\, C\in {\mathcal{C}}(n)\Bigg\}\leq n, $$ where $G_d$ is the set of elements of $G$ of order $d$, for some divisor $d$ of $n$. \end{theorem} \begin{proof} {First we consider two following facts:\\ {\bf{Fact 1}}. Suppose that $d$ is a divisor of $n$ and $G_d\neq \emptyset$. If $g,h\in G_d$ and $g$ and $h$ are adjacent in the power graph, then $g$ and $h$ generate the same cyclic group. So $\langle G_d\rangle$ is a disjoint union of cliques of size $\phi(d)$. Therefore; if $x$ is an element of a clique $H$ of $\langle G_d\rangle$ adjacent to an element $y$ of a clique $K$ of $\langle G_{d'}\rangle$, then every element of $H$ is adjacent to every element of $K$ and moreover, $d\mid d'$ or $d'\mid d$.\\ {\bf{Fact 2}}. Note that if $z$ is an element of order $d$, then for each divisor $d'$ of $d$, $z^{\frac{d}{d'}}$ is of order $d'$. So for each clique $T$ of $\langle G_d\rangle$, every element of $T$ is adjacent to every element of a clique $S$ of $\langle G_{d'}\rangle$.\\ Since $\{G_d\,:\, G\ {\rm has\ an\ element\ of\ order\ }d\}$ forms a partition for $G$, Fact $1$ implies that every maximal clique of $\mathcal{G}(G)$ has the form $Cl_1\cup\cdots \cup Cl_m$, where $Cl_i$ is a clique of $\langle G_{d_i}\rangle$ of size $\phi(d_i)$ and $\{d_1,\ldots,d_m\}$ is a chain of length $m$ belonging to ${\mathcal{C}}(n)$. Moreover; by Fact $2$, we deduce that for every chain $\{d_1,\ldots,d_m\}$ in ${\mathcal{C}}(n)$, there exists a clique for $\mathcal{G}(G)$ of this form. Now, by $|Cl_i|=\phi(d_i)$, we conclude that $$\omega(\mathcal{G}(G))=\max\Bigg\{\sum\limits_{\substack{d\in C\\ G_d\neq \emptyset}}\phi(d)\,:\, C\in {\mathcal{C}}(n)\Bigg\}\leq \sum_{d\mid n}\phi(d)=n.$$ Define a pre-ordering $\leq$ on $G$ by $x\leq y$ if and only if $x$ is a power of $y$. Clearly, the power graph of $G$ is the comparability graph of $\leq$ and so by Theorem \ref{comparabilitygraph}, the power graph of $G$ is perfect. Thus $\chi(\mathcal{G}(G))=\omega(\mathcal{G}(G))$ and the proof is complete.} \end{proof} The next two corollaries are direct consequences of Lemma \ref{chrombond} and Theorem \ref{main-theorem}. \begin{corollary} For every group $G$, the following statements are equivalent: \begin{enumerate} \item[\rm (i)] $\chi(\mathcal{G}(G))<\infty$; \item[\rm(ii)] $\omega(\mathcal{G}(G))<\infty$; \item[\rm(iii)] $G$ is bounded exponent. \end{enumerate} Moreover, the chromatic number of $\mathcal{G}(G)$ does not exceed the exponent of $G$. \end{corollary} \begin{corollary} Let $G$ be an abelian group of exponent $n$. Then $$\chi(\mathcal{G}(G))=\omega(\mathcal{G}(G))=\max\left\{\sum_{d\in C}\phi(d)\,:\, C\in {\mathcal{C}}(n)\right\}.$$ \end{corollary} \begin{corollary}\label{characteromega} Let $H$ be a subgroup of $G$ and $[G:H]<\infty$. Then $\omega({\mathcal{G}}(H))<\infty$ if and only if $\omega({\mathcal{G}}(G))<\infty$. \end{corollary} The following example shows that a similar assertion does not hold for the independence number. \begin{example} Let $G= C_2\times C_{2^\infty}$ and $H=\{0\}\times C_{2^\infty}$. Thus $[G:H]=2$. Since ${\mathcal{G}}(H)$ is a complete graph, $\alpha(H)=1$. Clearly, the set $\{1\}\times C_{2^\infty}$ is independent and so $\alpha(G)=\infty$. \end{example} \subsection{Miscellaneous properties}\label{misc} We conclude this section with three miscellaneous properties of the power graph of a group. \begin{theorem}\label{bipartite} If ${\mathcal {G}}(G)$ is a triangle-free graph, then $G$ is isomorphic to a direct product of $ C_2$ and ${\mathcal {G}}(G)$ is a star. \end{theorem} \begin{proof} {First we show that the order of every element of $G$ is at most 2. Let $a\in G$. %If $o(a)=\infty$, then $a, a^2$ and $a^4$ form a triangle, a contradiction. So $o(a)< \infty$. Now, If $o(a)\geq 3$, then $\{e,a,a^2\}$ is a triangle, a contradiction. So $G$ is an elementary abelian 2-group. Therefore, by Pr\"{u}fer-Baer Theorem, $G$ is isomorphic to a direct product of $ C_2$ and so ${\mathcal {G}}(G)$ is a star with the center $e$.} \end{proof} %\begin{thm}\label{alpha} %Let $H$ be an abelian subgroup of $G$ such that $[G:H]<\infty$. If $\alpha(\mathcal{G}(H))< \infty$, then $\mathcal{G}(G)$ contains no infinite independent set. %\end{thm} %\begin{proof} %{By contrary, suppose that $\mathcal{G}(G)$ contains an infinite independent set $I$. Since $[G:H]<\infty$, with no loss of generality, we can assume that there is an element $g_1\in I$ and an infinite subset $\{g_i\}_{i=1}^\infty$ of $I$ such that $g_iH=g_1H$, for every $i\geq1$. Now, let $T=\{g_1^{-1}g_i\,:\,i\geq 1$. Then $T$ is an infinite subset of $H$ and hence $H$ is infinite. We claim that $H$ is a bounded exponent group. To see this, by contrary assume that for every positive integer $n$, there exists $h_n\in H$ such that $o(h_n)>n$ On the other hand, since $H$ is abelian ????????} %\end{proof} The following theorem characterizes those groups whose power graphs are connected. \begin{theorem}\label{periodicdiameter} Let $G$ be a group. The following statements are equivalent. \begin{enumerate} \item[\rm(i)] ${\mathcal {G}}(G)$ is connected; \item[\rm(ii)] $G$ is periodic; \item[\rm(iii)] $\gamma({\mathcal {G}}(G))=1$; \item[\rm(iv)] ${\rm diam} ({\mathcal{G}}(G))\leq 2$. \end{enumerate} \end{theorem} \begin{proof} {(i)$\Longrightarrow$(ii) Let $x$ ($x\neq e$) be a vertex of ${\mathcal {G}}(G)$. We show that $x$ is of finite order in $G$. Since ${\mathcal {G}}(G)$ is connected, there is a path from $x$ to $e$. Let $y$ be the adjacent vertex to $e$ in this path. So the order of $y$ is finite. Now, suppose that $t$ is the adjacent vertex to $y$ in this path. Then the order of $t$ is finite, too. By repeating this procedure, we deduce that the order of $x$ is finite. So $G$ is periodic.\\ (ii)$\Longrightarrow$(iii) Since every element in $G$ has a finite order, $\{e\}$ is a dominating set.\\ The parts (iii)$\Longrightarrow$(iv) and (iv)$\Longrightarrow$(i) are clear.} \end{proof} \begin{theorem} If $\deg(g)<\infty$, for every $g\in G$, then $G$ is a finite group. \end{theorem} \begin{proof} {Let $g\in G$. Since $\deg(g)<\infty$, $g$ has a finite order in $G$. Thus $G$ is a periodic group and so $e$ is adjacent to every other vertices of $\mathcal{G}(G)$. Since $\deg(e)<\infty$, we deduce that $G$ is finite.} \end{proof} \begin{remark} Let $G\cong \prod_{i\geq 1} C_2$. Then $\mathcal{G}(G)$ is an infinite star with the center $0$. This shows that in the previous theorem the condition $\deg(g)<\infty$, for every $g\in G$ is necessary. \end{remark} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Power graph and commuting graph}\label{power-commuting} Let $G$ be a group. If the vertices $x$ and $y$ are joined in the power graph of $G$, then they are joined in the commuting graph; so the power graph is a spanning subgraph of the commuting graph. \begin{question}\label{power=commuting} For which groups is it the case that the power graph is equal to the commuting graph? \end{question} The identity is joined to all others in the commuting graph; so if the two graphs are equal, then $G$ is a periodic group. \begin{theorem}\label{powergraph-equals-commuting} Let $G$ be a finite group with power graph equal to commuting graph. Then one of the following holds: \begin{itemize} \item $G$ is a cyclic $p$-group; \item $G$ is a semidirect product of $C_{p^a}$ by $C_{q^b}$, where $p$ and $q$ are primes with $a,b>0$, $q^b\mid p-1$ and $C_{q^b}$ acts faithfully on $C_{p^a}$; \item $G$ is a generalized quaternion group. \end{itemize} \end{theorem} \begin{proof} {Let $G$ have power graph equal to commuting graph; that is, if two elements commute, then one is a power of the other. Then $G$ contains no subgroup isomorphic to $C_p\times C_q$, where $p$ and $q$ are primes, since this group fails the condition. A theorem of Burnside~\cite[Theorem 12.5.2]{hall} says that a $p$-group containing no $C_p\times C_p$ subgroup is cyclic or generalized quaternion. So all Sylow subgroups of $G$ are of one of these two types. Suppose that all Sylow subgroups are cyclic. Then $G$ is metacyclic \cite[Theorem 9.4.3]{hall}. The cyclic normal subgroup of $G$ has order divisible by one prime only, say $p$. Its centraliser in $G$ is a Sylow $p$-subgroup $P$ of $G$, since it contains no elements of order coprime to $p$. Hence $G$ is a semidirect product of $P$ and a cyclic group $Q$ of order coprime to $p$, necessarily a cyclic $q$-group for some prime $q$. If $|Q|=q^b$, then we have $q^b\mid p-1$. So we may suppose that $G$ has generalized quaternion Sylow $2$-subgroups. By Glauberman's Z*-Theorem~\cite{glauberman}, $G/O(G)$ has a central involution, where $O(G)$ is the maximal normal subgroup of $G$ of odd order. This involution must act fixed-point-freely on $O(G)$, so $O(G)$ is abelian, and hence cyclic of prime power order. But a generalized quaternion group cannot act faithfully on such a group. So $O(G)=1$. Then the involution in $G$ is central, so $G$ is a $2$-group, necessarily a generalized quaternion group.} \end{proof} \begin{remark} In the infinite case, there are other examples, such as \emph{Tarski monsters}, which are infinite groups whose non-trivial proper subgroups are all cyclic of prime order $p$. Probably no classification is possible. \end{remark} %Now, we extend our Theorem \ref{powergraph-equals-commuting} to solvable groups. In the next theorem, we extend Theorem \ref{powergraph-equals-commuting} to solvable groups. \begin{theorem} Let $G$ be a solvable group with power graph equal to commuting graph. Then one of the following holds: \begin{itemize} \item $G$ is a cyclic $p$-group; \item $G$ is a semidirect product of $C_{p^a}$ by $C_{q^b}$, where $p$ and $q$ are primes with $a,b>0$, $q^b\mid p-1$ and $C_{q^b}$ acts faithfully on $C_{p^a}$; \item $G$ is a generalized quaternion group; \item $G$ is the $p$-quasicyclic group $C_{p^\infty}$; \item $G$ is a semidirect product of $p$-quasicyclic group $C_{p^\infty}$ and a finite cyclic group. \end{itemize} \end{theorem} \begin{proof} { We use this fact that every finitely generated periodic solvable group is finite. We know that $G$ is periodic. We show that there are no three elements whose order are distinct primes. Suppose that $o(a)=p$, $o(b)=q$ and $o(c)=r$, where $p$, $q$ and $r$ are distinct primes. Let $H$ be the subgroup generated by $a$, $b$ and $c$. Then $H$ is finite. Clearly, the power graph and the commuting graph of $H$ are equal. This contradicts Theorem \ref{powergraph-equals-commuting}. Thus the order of every finite subgroup of $G$ is $p^\alpha q^\beta$, for some non-negative integers $\alpha$ and $\beta$. By the second part of Theorem \ref{powergraph-equals-commuting}, we may assume that $\beta$ is bounded, because $q^\beta | p-1$. Also, by Theorem \ref{powergraph-equals-commuting}, the order of every element of $G$ is a $p$-power or a $q$-power, because every cyclic subgroup is a $p$-group or a $q$-group. If $\alpha, \beta >0$, then by the second part of Theorem \ref{powergraph-equals-commuting}, $\langle a, b \rangle $ is semidirect product of $\langle a \rangle$ and $\langle b \rangle$. So, $\langle a \rangle$ and $\langle b \rangle$ are both cyclic (even in the case $q=2$). Let $N$ be the set of all elements of $G$ whose orders are $p$-power. We show that $N$ is an abelian normal subgroup of $G$. To see this first we show that if $x$ and $y$ are two elements of $N$, then $xy=yx$. Let $S$ be the subgroup generated by $x$ and $y$. Then $S$ is a finite group of order $p^\alpha q^\beta$. If $\beta=0$, then by Theorem \ref{powergraph-equals-commuting}, $S$ is a cyclic $p$-group and we are done. So assume that $\beta>0$. Let $N_1$ and $Q$ be Sylow $p$-subgroup and Sylow $q$-subgroup of $S$, respectively. Then by Theorem \ref{powergraph-equals-commuting} both are cyclic. Now, by \cite[Theorem 6.2.11]{scott}, $Q$ has a normal complement. So, $N_1\lhd S$. This implies that $x,y\in N_1$ and so $xy=yx$. Thus we conclude that $N$ is an abelian $p$-subgroup of $G$. Now, by the definition of $N$, $N\lhd G$. Now, let $Q$ be a $q$-subgroup of $G$ which has maximum size. We prove that $G=NQ$. Let $a\in G$ be an element of $G$ whose order is $q$-power. Let $M$ be the subgroup generated by $a$ and $Q$. Then $M=P_1Q_1$, where $P_1$ and $Q_1$ are Sylow $p$-subgroup and Sylow $q$-subgroup of $M$, respectively and $P_1\lhd M$. But $Q_1$ is a conjugate of $Q$ and so $M=P_1Q$. Since $a\in M$, we have $a=bc$, where $b\in P_1$ and $c\in Q$. But $P_1\subseteq P$ and this implies that $a\in PQ$, as desired. So $G=NQ$. Since $N$ is an abelian group, the commuting graph of $N$ and so the power graph of $N$ is a complete graph. Now, Theorem \ref{alphapgroup} yields that $N$ is finite or $N=Z_{p^\infty}$. } \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The enhanced power graph} \subsection{Definition and properties} In the Section \ref{sec-power-graph} we investigated some properties of power graphs of groups. In Theorem \ref{powergraph-equals-commuting}, we characterized finite groups for which the power graph is the same as the commuting graph. Now, it is natural to ask if they are not equal, how close these graphs are. To tackle this problem we introduce an intermediate graph. This graph can be regarded as a measurement for this difference. Given a group $G$, the \emph{enhanced power graph} of $G$ denoted by $\mathcal{G}_e(G)$ is the graph with vertex set $G$, in which $x$ and $y$ are joined if and only if there exists an element $z$ such that both $x$ and $y$ are powers of $z$. The power graph and commuting graph behave well on restriction to a subgroup (that is, if $H\le G$, then the power graph of $H$ is the induced subgraph of the power graph of $G$ on the set $H$, and similarly for the commuting graph). Because of the existential quantifier in the definition, it is not obvious that the same holds for the enhanced graph. That this is so is a consequence of the fact that $x$ and $y$ are joined in the enhanced power graph if and only if $\langle x,y\rangle$ is cyclic. Note that \begin{itemize} \item the power graph is a spanning subgraph of the enhanced power graph; \item the enhanced power graph is a spanning subgraph of the commuting graph. \end{itemize} In the next remark, we use the concept of graph squares. For a graph $H$, the \textit{square} of $H$ is a graph with the same vertex set as $H$ in which two vertices are adjacent if their distance in $H$ is at most two. \begin{remark} If we assume that the (undirected or directed) power graph has a loop at each vertex, then the enhanced power graph lies between the power graph and its square. We already saw that it contains the power graph (as a spanning subgraph). Now, let $x$ and $y$ be two vertices joined by a path $(x,z,y)$ of length $2$ in the power graph. There are four cases in the directed power graph $D=\vec{\mathcal{G}}(G)$: \begin{itemize}\itemsep0pt \item $(x,z),(z,y)\in E(D)$. Then $x$ is a power of $z$, and $z$ a power of $y$; so $x$ is a power of $y$, and $(x,y)\in E(D)$. \item $(z,x),(y,z)\in E(D)$. Dual to the first case. \item $(x,z),(y,z)\in E(D)$. Then $x$ and $y$ are powers of $z$, so they are joined in the square of the power graph. \item $(z,x),(z,y)\in E(D)$. In this case there is nothing we can say. \end{itemize} \end{remark} Also the following holds: \begin{theorem} Let $G$ and $H$ be finite groups. If the power graphs of $G$ and $H$ are isomorphic, then their enhanced power graphs are also isomorphic. \end{theorem} \begin{proof} {Note that $x$ and $y$ are joined in the enhanced power graph if and only if there is a vertex $z$ which dominates both in the directed power graph. So the theorem follows from the main theorem of~\cite{cameron}.} \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Comparing to the power graph and commuting graph} \begin{question} For which (finite) groups is the power graph equal to the enhanced power graph? \end{question} This question connects with another graph associated with a finite group, the \emph{prime graph}, defined by Gruenberg and Kegel~\cite{gk}: the vertices of the prime graph of $G$ are the prime divisors of $|G|$, and vertices $p$ and $q$ are joined if and only $G$ contains an element of order $pq$. To state the next result we need a definition. The group $G$ is a \emph{$2$-Frobenius group} if it has normal subgroups $F_1$ and $F_2$ such that $F_1