The Complexity of Power Graphs Associated With Finite Groups

Abstract

The power graph $\mathcal{P}(G)$ of a finite group $G$ is the graph whose vertex set is $G$, and two elements in $G$ are adjacent if one of them is a power of the other. The purpose of this paper is twofold. First, we find the complexity of a clique--replaced graph and study some applications. Second, we derive some explicit formulas concerning the complexity $\kappa (\mathcal{P}(G))$ for various groups $G$ such as the cyclic group of order $n$, the simple groups $L_2(q)$, the extra--special $p$--groups of order $p^3$, the Frobenius groups, etc.

14 pages