Power graphs: A survey

Jemal Abawajy^a , Andrei Kelareva,b , Morshed Chowdhury^a

^aSchool of Information Technology, Deakin University 221 Burwood Hwy, Burwood, Melbourne, Victoria 3125, Australia ^bCARMA Priority Research Center, School of Mathematical and Physical Sciences University of Newcastle, University Drive, Callaghan, Newcastle, NSW 2308, Australia

{jemal.abawajy,morshed.chowdhury}@deakin.edu.au, andreikelarev-deakinuniversity@yahoo.com

This article gives a survey of all results on the power graphs of groups and semigroups obtained in the literature. Various conjectures due to other authors, questions and open problems are also included.

Keywords: power graphs, Eulerian graphs, Hamiltonian graphs, connectivity. Mathematics Subject Classification : 05C25, 05C40, 05C45, 05C78.

1. Introduction

Many interesting results on the power graphs have been obtained recently. This article gives a survey of the current state of knowledge on this research direction by presenting all results and open questions recorded in the literature dealing with power graphs. Various conjectures formulated by other authors and several new open problems are also included. This is the first survey devoted to the power graphs.

2. Definition of power graphs

Let us begin with the definitions of the directed and undirected power graphs, which are the main concepts considered in this survey. In the literature, the power graphs have been defined and considered for groups and semigroups. Section 4 contains concise prerequisites on the terminology

Received: 5 October 2013, Revised: 23 October, Accepted: 26 October 2013.

of the group and semigroup theories used in the results (cf. [30, 79]). It is well known that the operation in every group or semigroup is power-associative, i.e., the powers of each element do not depend on the order in which the operation in the power is performed (see Section 4 for details). Therefore the following definition applies to all groups and semigroups.

Definition 1. Let S = (S, ·) be a set with a power-associative operation ·. The directed power graph −→^G (S) of ^S is a directed graph with the set ^S of vertices and with all edges (u, v) such that u 6= v and v is a power of u. The undirected power graph G (S) of S is the underlying undirected graph of −→^G (S). This means that the set of vertices of ^G (S) is equal to ^S and two distinct vertices are adjacent if and only if one of them is a power of the other.

Figure 1. The directed power graph of the cyclic group Z6.

Figure 2. The undirected power graph of the cyclic group Z6.

The directed power graph could also be called the power digraph, although the latter term has not been used in the literature yet. We include Figures 1 and 2 with the directed power graph \(\overrightarrow{\mathcal{G}}(\mathbb{Z}_6)\) and undirected power graph \(\mathcal{G}(\mathbb{Z}_6)\).

Definition 2. If G is a group with identity e and \(\overrightarrow{\mathscr{G}}(G)\), \(\mathscr{G}(G)\) are the directed and undirected power graphs of G, respectively, then the graphs obtained by deleting the vertex e from \(\overrightarrow{\mathscr{G}}(G)\) and \(\mathscr{G}(G)\) are denoted by \(\overrightarrow{\mathscr{G}}^*(G) = \overrightarrow{\mathscr{G}}(G) - \{e\}\) and \(\mathscr{G}^*(G) = \mathscr{G}(G) - \{e\}\), respectively.

For clarity, formulating all results in this article we use only complete terms 'directed power graph' and 'undirected power graph'. The shorter expression 'power graph' is used here only when we refer to both of these concepts simultaneously and in general discussions that may apply to both of these notions.

3. Historical comments

The concept of a directed power graph was first introduced and considered in [43] in the case of groups. For semigroups, it was first investigated in [47], and then in [44, 46]. All of these papers used only the brief term 'power graph' to refer to the directed power graph, with the understanding that the undirected power graph is the underlying undirected graph of the directed power graph.

The undirected power graphs became the main focus of study in [24] and in the subsequent papers by P. J. Cameron et al. [22, 23], which introduced the use of the brief term 'power graph' in the second meaning of an undirected power graph. For a group G, the digraph \(\mathcal{G}^*(G)\) was considered in [76] as the main object of study.

Thus, the readers may need to be aware that in the literature the brief term 'power graph' can mean either a 'directed power graph' or an 'undirected power graph' depending on which type of graphs is the main subject of study in each particular paper. For clarity, the present article states all results using only the complete terms 'directed power graph' and 'undirected power graph'.

4. Preliminaries and background information

We use standard terminology and refer the readers to [25, 30, 36, 37, 60, 78, 79] for more details, further bibliography and explanations.

Throughout \(\mathbb{Z}\) and \(\mathbb{N}\) denote the set of all integers and all positive integers, respectively, and \(\mathbb{N}_0 = \mathbb{N} \cup \{0\}\) stands for the set of all natural numbers. The Euler totient function of a positive integer n is denoted by \(\phi(n)\).

All graphs considered in this paper are assumed to be simple. In particular, they do not have loops. If D=(V,E) is a directed graph, then the underlying undirected graph of D is the undirected graph with the same set V of vertices, where two distinct vertices u and v are adjacent if and only if \((u,v) \in E\) or \((v,u) \in E\).

Subsequent sections of this survey article are organised according to the graph theoretical properties being considered, and the definitions of these properties are reviewed in the following sections. The rest of this section contains concise preliminaries concerning groups and semigroups.

An operation or a binary operation on a set S is a mapping from the direct product \(S \times S\) to S. If \(\circ\) is a binary operation on a set S and \(x, y \in S\), then the image of the pair (x, y) under \(\circ\) is

denoted by \(x \circ y\), which is called the infix notation for the operation \(\circ\). In additive terminology and notation the operation \(\circ\) is denoted by + and is called addition, so that the result of the operation is written down as x + y. In multiplicative terminology and notation the operation \(\circ\) is referred to as multiplication and is denoted by \(\cdot\) so that the result of the operation is recorded as \(xy = x \cdot y\). In this survey we use multiplicative notation to discuss sets with a binary operation. A set with a binary operation is called a magma [19, 29] or a groupoid [87].

An operation \(\cdot\) on the set S is associative if it satisfies the following associative law: x(yz) = (xy)z for all \(x, y, z \in S\). A semigroup is a set S equipped with an associative binary operation \(\cdot\). For example, the set of positive integers is a semigroup with respect to addition, and at the same time it is a semigroup with respect to multiplication. If we want to distinguish between these two semigroups on the same set, we can indicate the corresponding operation explicitly by using the symbols \((\mathbb{N}, +)\) or \((\mathbb{N}, \cdot)\), respectively.

Let \(M=(M,\cdot)\) be a magma. A subset S of M is called a submagma of M if it is closed for the operation of M, i.e., if \(x,y\in S\) implies \(xy\in S\). The intersection of all submagmas of M that contain S is the smallest submagma of M containing S. It is denoted by \(\langle S \rangle\). An operation \(\cdot\) on M is said to be power-associative if the submagma \(\langle x \rangle\) is associative, for every \(x\in M\). In particular, every semigroup is power-associative.

An element e of a semigroup S is called an identity or an identity element of S if xe = ex = x for all \(x \in S\). It is well known and easy to verify that a semigroup cannot have two distinct identity elements. This means that if a semigroup has an identity, then the identity is unique.

Let S be a semigroup with identity e, and let \(x \in S\). An element \(y \in S\) is called an inverse of x if xy = yx = e. It is also well known and easy to prove that if an element x has an inverse, then the inverse is unique. The inverse of x is denoted by \(x^{-1}\), as no ambiguity can arise. A group is a semigroup with identity where every element has an inverse.

Let G be a group. The cardinality |G| is also called the order of G. For \(n \in \mathbb{N}\), the cyclic group of order n can be defined as the group \(\mathbb{Z}_n = \mathbb{Z}/n\mathbb{Z}\) of residues modulo n.

A subgroup of G is a subset of G that is a group with the same identity and with respect to the same operation. In particular, every subgroup H of G is closed for the operation of the group, which means that \(xy \in H\) for all \(x, y \in H\). Besides, if H is a subgroup of G, then \(x^{-1} \in H\) for all \(x \in H\). A subgroup H of G is said to be normal if \(g^{-1}hg \in H\) for all \(h \in H\), \(g \in G\). If H is a subgroup of G, then we write H < G. If H is a normal subgroup of G, then we write H < G. If H is a maximal subgroup of G, then we write H < G.

For any subset T of G, the intersection of all subgroups of G that contain T is the smallest subgroup of G containing T. It is denoted by \(\langle T \rangle\) and is called the subgroup generated by T in G. In particular, the set \(\langle g \rangle = \{g^n \mid n \in \mathbb{Z}\}\) is the cyclic group generated by g in G.

The order of the element x in a group or a semigroup is defined as the cardinality of \(\langle x \rangle\). The order of x is denoted by o(x). A group is said to be torsion if all of its elements have finite order.

The set of all elements of G of order k is denoted by \(\Omega_k(G)\). The set of the orders of all elements of G is denoted by \(\pi(G)\) and is called the spectrum of G. The exponent of a finite group G is the least common multiple of the orders of all elements of G. It is denoted by Exp(G).

Let p be a prime. Then all elements with orders equal to a power of p form a subgroup of G called a primary component of G, or a p-primary component of G. The p-primary component of a group G is denoted by \(G_p\). A group G is called a p-group if \(G = G_p\), i.e., if the order of every

element of G is a power of p.

A group G is said to be an EPO-group, if the orders of all nontrivial elements of G are prime. An EPPO-group is a group where the order of every nontrivial element is a power of a prime.

The dihedral group \(D_{2n}\) is defined by the following presentation

\[D_{2n} = \langle x, y \mid x^n = y^2 = e, y^{-1}xy = x^{-1} \rangle.\]

The semi-dihedral group \(SD_{2^n}\) is presented by

\[SD_{2^n} = \langle x, y \mid x^{2^n - 1} = y^2 = e, yxy = x^{2^{n-2} + 1} \rangle.\]

The symmetric group \(\mathbb{S}_n\) on a finite set of n letters is the group consisting of all permutations of these n letters with respect to the operation of composition of permutations, regarded as functions.

Let \(S=(S,\cdot)\) be a semigroup. An equivalence relation \(\varrho\) on S is called a congruence if it is compatible with the operation \(\cdot\) of S, that is if \((x,y)\in\varrho\) implies \((xz,yz)\in\varrho\) and \((zx,zy)\in\varrho\) for all \(x,y,z\in S\). If \(\varrho\) is a congruence, then we can define an operation on the set \(S/\varrho\) of all equivalence classes of \(\varrho\) by the rule [x][y]=[xy], where [x] stands for the equivalence class containing x. This means that the product of two classes is the class containing the product of representatives of these classes. This definition makes sense, because it is easy to verify that the resulting class [xy] depends only on the whole classes [x] and [y], but does not depend on the choice of particular representatives x and y. It follows that the set \(S/\varrho\) is a semigroup too. It is called the quotient semigroup of S modulo \(\varrho\).

Now let S be a semigroup, and let T be a subset of S. Then the intersection of all subsemigroups of S containing T is the smallest subsemigroup of S containing T. It is denoted by \(\langle T \rangle\) and is called the subsemigroup of S generated by T. In particular, for any \(x \in S\), the subsemigroup \(\langle x \rangle\) coincides with the set \(\{x^n \mid n \in \mathbb{N}\}\). The ideal (left ideal or right ideal) generated by T in S is the smallest subsemigroup I containing T and such that \(GI \cup IG \subseteq I\) (respectively, \(GI \subseteq I\), \(IG \subseteq I\)).

Let S be a semigroup with an ideal I. Then the Rees quotient semigroup S/I is the semigroup with zero \(\theta\) obtained from S by identifying all elements of the ideal I with \(\theta\). If S has zero \(\theta\) and \(I = \{\theta\}\), then S/I = S.

An element of a semigroup is said to be periodic if it has a finite order. A semigroup entirely consisting of periodic elements is called a periodic semigroup.

An operation on a set S is commutative if it satisfies the commutative law, i.e., if xy = yx for all \(x, y \in S\). An abelian group is a group with commutative operation. A semigroup satisfying the commutative law is said to be commutative.

For a prime p, a group G is called an elementary abelian p-group if G is finite, abelian and every nontrivial element of G has order p. The quasicyclic p-group is the infinite group denoted by \(C_{p^{\infty}}\) that has generators \(g_1, g_2, \ldots\) such that \(g_1^p = e\) and \(g_i^p = g_{i-1}\), for all i > 1, where e is the identity of the group. Quasicyclic groups are the only infinite abelian groups all subgroups of which are finite.

Let G be a group with a subgroup H. A right (left) coset of the subgroup H is a set of the form Hg (respectively, gH), where \(g \in G\). The set of left cosets has the same cardinality as the set of right cosets, and this cardinality is called the index of H in G. If N is a normal subgroup,

then the quotient group G/N is the set of all right cosets of N in G with the following operations: (Ng1)(Ng2) = Ng1g² and (Ng) ⁻¹ = Ng⁻¹ , for all g, g1, g² ∈ G.

The center of a semigroup S is the set Z(S) = {z ∈ S | ∀x ∈ S : xz = zx} consisting of those elements that commute with all elements of S. The center of every group G is a normal subgroup of G. A group G is said to be center-by-finite if the quotient group G/Z(G) is finite.

Rees matrix semigroups are very well known in semigroup theory and play crucial roles in describing the structure of semigroups (cf. [30]). For examples of applications of these concepts, let us also refer to [1, 55, 56, 54, 57]. Suppose that G is a group, and I, Λ are nonempty sets. Let P = [pλi] be a (Λ × I)-matrix with entries pλi ∈ G⁰ , for all λ ∈ Λ, i ∈ I. The Rees matrix semigroup M⁰ (G; I,Λ; P) over G with sandwich-matrix P consists of zero θ and all triples (g;i, λ), where g ∈ G⁰ , i ∈ I, λ ∈ Λ, where all triples (θ;i, λ) are identified with θ, and where multiplication is defined by the rule (g1;i1, λ1)(g2;i2, λ2) = (g1p^λ1i² g2;i1, λ2), for all g1, g² ∈ G, i1, i² ∈ I, λ1, λ² ∈ Λ.

A semigroup S is said to be regular if, for each x ∈ S, there exists y ∈ S such that xyx = x. An element x of S is called an idempotent if x ² = x.

5. Eulerian graphs

A walk is a list v0, e1, v1, . . . , ek, v^k of vertices and edges such that, for 1 ≤ i ≤ k, the edge eⁱ has endpoints vi−¹ and vⁱ . A trail is a walk without repeated edges. An Eulerian circuit of an undirected graph is a closed walk that traverses every edge of the graph exactly once. An Eulerian graph is a graph with an Eulerian circuit.

Theorem 5.1. ([26]) The undirected power graph of any finite group of even order is not Eulerian.

Proposition 5.1. ([26]) For n ≥ 5, the undirected power graph of the dihedral group D2ⁿ is not Eulerian.

Proposition 5.2. ([77]) Let G be a finite group. Then the undirected power graph G (G) is Eulerian if and only if |G| is odd.

Theorem 5.2. ([76]) Let G be a finite group. Then G ∗ (G) is Eulerian if and only if G is a cyclic 2-group or a generalized quaternion 2-group.

6. Hamiltonian graphs

Proposition 6.1. ([77]) Let G be a finite p-group. Then the undirected power graph G (G) has a Hamiltonian cycle if and only if |G| 6= 2 and G is cyclic.

Proposition 6.2. ([77]) Let p be an odd prime. Then the undirected power graph of a p-group is 2-connected if and only if it is Hamiltonian.

Denote by Uⁿ the group of units of the ring Zn.

Problem 1. ([24]) Describe all positive integers n such that the undirected power graph G (Un) is Hamiltonian.

Theorem 6.1. ([24]) Let \(n \geq 3\). Then the graph \(\mathcal{G}(U_n)\) is not Hamiltonian for \(n = 2^m p_1 \cdots p_k\), where \(p_1, \ldots, p_k\) are distinct Fermat primes, m and k are nonnegative integers, \(m \geq 2\) for k = 0, 1, and \(k \geq 2\) for m = 0, 1.

It was conjectured in [24, p. 426] that the undirected power graph \(\mathcal{G}(U_n)\) is Hamiltonian for all values \(n \geq 3\) with the exception of \(n = 2^m p_1 \cdots p_k\), where \(p_1, \dots, p_k\) are distinct Fermat primes, m and k are nonnegative integers, \(m \geq 2\) for k = 0, 1 and \(k \geq 2\) for m = 0, 1. The following collection of counterexamples to this conjecture was given in [77, Lemma 3].

Proposition 6.3. ([77]) If \(n = 2^v \times 3^2\), where \(v \ge 3\), or \(n = 2^t \times 7\), where \(t \ge 2\), or \(n = 2^2 3^2 p\), where p is a Fermat prime, then the undirected power graph \(\mathcal{G}(U_n)\) does not have a Hamiltonian cycle.

Theorem 6.2. ([24]) If \(n \geq 3\) is an integer, then \(\mathscr{G}(\mathbb{Z}_n)\) is Hamiltonian.

7. Complete graphs

An undirected graph D=(V,E) is said to be complete if any two distinct vertices of D are adjacent.

Theorem 7.1. ([24]) Let S be a semigroup. Then the undirected power graph \(\mathcal{G}(S)\) is complete if and only if the cyclic subsemigroups of S are linearly ordered with respect to the containment relation \(\subseteq\).

Theorem 7.2. ([24]) A finite group has a complete undirected power graph if and only if it is cyclic and has order equal to \(p^m\), where p is a prime and m is a nonnegative integer.

Theorem 7.3. ([24]) The undirected power graph \(\mathcal{G}(U_n)\) is complete if and only if \(n \in \{1, 2, 4, p, 2p\}\), where p is a Fermat prime, i.e., \(p = 2^{2^m} + 1\) for \(m \in \mathbb{Z}\), m > 0.

Theorem 7.4. ([77]) Let G be a finite p-group. Then the undirected power graph \(\mathcal{G}(G)\) is a union of complete subgraphs which share the identity element of G if and only if G is isomorphic to a cyclic group, a p-group of exponent p, or a dihedral group.

8. Edge number

Theorem 8.1. ([24]) For each finite group G, the number of edges of the undirected power graph \(\mathcal{G}(G)\) is given by the formula

\[E(\mathcal{G}(G)) = \frac{1}{2} \sum_{g \in G} \{2o(g) - \phi(o(g)) - 1\}.\]

Corollary 8.1. ([24]) The number of edges of the undirected power graph \(\mathcal{G}(\mathbb{Z}_n)\) is given by \(\frac{1}{2} \sum_{d|n} \{2d - \phi(d) - 1\} \phi(d)\).

Theorem 8.2. ([2]) Among all finite groups of a given order, the cyclic group of that order has the largest number of edges in its directed power graph.

Theorem 8.3. ([70]) The undirected power graph \(\mathcal{G}(\mathbb{Z}_{p^n})\) has the maximum number of edges among all undirected power graphs of p-groups of order \(p^n\).

A conjecture was recorded in [70, Conjecture 2] that Theorem 8.3 remains valid for finite groups of any order. This conjecture was proved in [75].

Theorem 8.4. ([75]) The undirected power graph \(\mathcal{G}(\mathbb{Z}_n)\) has the maximum number of edges among all undirected power graphs of groups of order n.

Several criteria for the nonsimplicity of G have been obtained in [76].

Theorem 8.5. ([77]) If G is a finite simple group of order n, then \(|E(\mathcal{G}(G))| \leq |E(\mathcal{G}(\mathbb{Z}_n))|\).

Corollary 8.2. ([76]) Let G be a finite group of order \(n = p_1^{a_1} \cdots p_k^{a_k}\), where k > 1, \(a_1, \ldots, a_k \ge 1\), and where \(p_1, \ldots, p_k\) are pairwise distinct prime numbers. If \(d(\mathscr{G}^*(G)) = 3\), then G is not simple.

The degree of x in \(\mathcal{G}(G)\) is denoted by deg(x).

Proposition 8.1. ([76]) Let G be a finite group, and let p be the greatest prime divisor of |G|. If there exists a vertex x in \(\mathscr{G}^*(G)\) with \(\deg(x) \geq |G|/p\), then G is not simple.

Proposition 8.2. ([76]) Let G be a finite group, and let q be the smallest prime divisor of |G|. If there exists a vertex \(x \neq e\) in \(\mathcal{G}(G)\) such that \(\deg(x) \geq |G|/q\), then \(Z(G) \neq \{e\}\).

9. Chromatic number

The chromatic number \(\chi(G)\) of an undirected graph G is the smallest positive integer k such that the vertices of G can be coloured in k colours so that no two adjacent vertices share the same colour. A graph G is said to be planar if it can be drawn on a plane without any crossing of its edges.

Theorem 9.1. ([26]) If \(n = p^m\), for some prime p and for some \(m \in \mathbb{N}\), then \(\chi(\mathcal{G}(D_{2n})) = n\) and \(\chi(\mathcal{G}(\mathbb{S}_n)) > n\). Moreover, for all such n with \(n \geq 5\), the undirected power graph \(\mathcal{G}(\mathbb{S}_n)\) is not planar.

Theorem 9.2. ([26]) The undirected power graph \(\mathcal{G}(D_{2n})\) is not planar in each of the following two cases:

• (i) \(n = p^m\), for some prime \(p, m \in \mathbb{N}\) and n > 5;
• (ii) n = 2p, for some odd prime p.

A full exponent group is a group G such that Exp(G) = o(x), for an element \(x \in G\).

Theorem 9.3. ([70]) Let G be a full exponent group such that \(\text{Exp}(G) = p_1^{b_1} \cdots p_k^{b_k}\), where \(p_1, \dots, p_k\) are prime numbers and \(b_1, \dots, b_k \in \mathbb{N}_0\). Then

\[\omega(\mathscr{G}(G)) = \chi(\mathscr{G}(G)) = p_k^{b_k} + \sum_{j=0}^{k-2} \left( p_{k-j-1}^{b_{k-j-1}} - 1 \right) \left( \prod_{i=0}^j \phi(p_{k-i}^{b_{k-i}}) \right).\]

Conjecture 1. ([70]) Theorem 9.3 remains valid for all finite groups.

A complete list of the chromatic numbers of the undirected power graphs of nonabelian groups of order up to 14 are determined and listed in [26].

10. Clique number

Suppose D=(V,E) is a graph. A subset X of the vertices of D is called a clique if it induces a complete graph of D. The maximum size of a clique in D is called the clique number of D and denoted by \(\omega(D)\).

A subset Y of D is called an independent set if it induces a null subgraph in D. The maximum size of an independent set is called the independence number of D and denoted by \(\alpha(D)\).

Theorem 10.1. ([70]) Let \(n = p_1^{a_1} \cdots p_k^{a_k}\), where \(p_1 < \cdots < p_k\) are prime numbers and \(a_1, \ldots, a_k \in \mathbb{N}_0\). Then the clique number and chromatic number of the undirected power graph \(\mathcal{G}(\mathbb{Z}_n)\) are determined by the following formula

\[\omega(\mathscr{G}(\mathbb{Z}_n)) = \chi(\mathscr{G}(\mathbb{Z}_n)) = p_k^{a_k} + \sum_{j=0}^{k-2} \left( p_{k-j-1}^{a_{k-j-1}} - 1 \right) \left( \prod_{i=0}^j \phi(p_{k-i}^{a_{k-i}}) \right).\]

In order to describe the power graphs of all finite abelian groups, we take any finite abelian group G and any elements a,b in G, and introduce the following notation. Denote the primary components of G by \(G_{p_1},\ldots,G_{p_n}\), and express each \(G_{p_i}\) as a direct product of cyclic groups \(G_{p_i}=(C_{p_i^{w_{i,1}}})^{q_{i,1}}\times(C_{p_i^{w_{i,2}}})^{q_{i,2}}\times\cdots\times(C_{p_i^{w_{i,m_i}}})^{q_{i,m_i}}\) and \(w_{i,1}< w_{i,2}<\cdots< w_{i,m_i}\). For \(i=1,\ldots,n\), denote the projections of a and b on \(G_{p_i}\), by \(a_i\) and \(b_i\), respectively. Choose generators \(g_{i,j,k}\) in the cyclic groups of \(G_{p_i}\) above, where \(1\leq j\leq m_i\) and \(1\leq k\leq q_{i,j}\). Write \(a_i\) and \(b_i\) in the form \(a_i=g_{i,1,1}^{c_{i,1,1}}\ldots g_{i,m_i,q_{i,m_i}}^{c_{i,m_i,q_{i,m_i}}}\), and \(b_i=g_{i,1,1}^{d_{i,1,1}}\ldots g_{i,m_i,q_{i,m_i}}^{d_{i,m_i,q_{i,m_i}}}\), where \(c_{i,j,k}=u_{i,j,k}p_i^{w_{i,j}-r_{i,j,k}}\), \(d_{i,j,k}=v_{i,j,k}p_i^{w_{i,j}-s_{i,j,k}}\) and \((u_{i,j,k},p_i)=1\), \((v_{i,j,k},p_i)=1\). The following theorem describes the directed power graphs of all finite abelian groups.

Theorem 10.2. ([43]) Let G be a finite abelian group, and let a, b be any elements of G. Suppose that the prime factorization of the order of a is \(|a| = \prod_{i=1}^n p_i^{t_i}\), where \(1 \le t_i \le w_{i,m_i}\). Then

• (a) a belongs to a clique of order \(\phi(|a|)\);
• (b) (a,b) is an edge of the directed power graph of G if and only if, for every \(i=1,\ldots,n\),

\[p_i^{w_{i,j}} | v_{i,j,k} u_{i,j,k}^{\phi(p_i^{w_{i,j}})-1} p_i^{r_{i,j,k}-s_{i,j,k}} - v_{i,j',k'} u_{i,j',k'}^{\phi(p_i^{w_{i,j'}})-1} p_i^{r_{i,j',k'}-s_{i,j',k'}},\]

for all \(1 \le j \le j' \le m_i\), and \(1 \le k \le k' \le q_{i,j'}\).

(c) If \(w_{i,h_i}\) is the smallest exponent in \(G_{p_i}\) such that \(t_i \leq w_{i,h_i}\) then \(\overrightarrow{\mathscr{G}}(G)\) contains

\[\prod_{i=1}^{n} \frac{(p_i^{w_{i,1}})^{q_{i,1}} (p_i^{w_{i,2}})^{q_{i,2}} \dots (p_i^{w_{i,h_{i-1}}})^{q_{i,h_{i-1}}} ((p_i^{t_i})^{q_{i,h_i}+\dots+q_{i,m_i}} - (p_i^{t_i-1})^{q_{i,h_i}+\dots+q_{i,m_i}})}{(p_i^{t_i} - p_i^{t_i-1})}\]

cliques of order \(\prod_{i=1}^{w} (p_i^{t_i} - p_i^{t_i-1})\), for each \(t_i\). Here we replace \((p_i^{t_i} - p_i^{t_i-1})\) by 1, if \(t_i = 0\).

11. Planarity

Theorem 11.1. ([70]) Let G be a finite group. Then the undirected power graph \(\mathcal{G}(G)\) is planar if and only if \(\pi_e(G) \subseteq \{1, 2, 3, 4\}\).

Corollary 11.1. ([70]) The undirected power graph of a cyclic group of order n is planar if and only if \(n \in \{2, 3, 4\}\).

Corollary 11.2. ([24]) The undirected power graph of \(U_n\) is planar if and only if n divides 240.

Corollary 11.3. ([70]) \[\chi(\mathscr{G}(D_{2n})) = \omega(\mathscr{G}(D_{2n})) = \chi(\mathscr{G}(\mathbb{Z}_n)).\]

Corollary 11.4. ([70]) The undirected power graph \(\mathcal{G}(SD_{2^n})\) is a union of a complete graph of order \(2^n\) and \(2^n\) copies of \(K_2\) that share the identity vertex. For n > 3, this graph is neither Eulerian, nor Hamiltonian, nor nonplanar. Moreover, \(\chi(\mathcal{G}(SD_{2^n})) = \omega(\mathcal{G}(SD_{2^n})) = \alpha(\mathcal{G}(SD_{2^n})) = 2^n\).

Theorem 11.2. ([70]) Suppose that \(n = p_1^{b_1} \cdots p_k^{b_k}\) is the prime power decomposition of n and \(m = b_1 + \cdots + b_k\). Then \(\alpha(\mathcal{G}(\mathbb{Z}_n))\) is the coefficient of the middle term or the two middle terms of \(\prod_{i=1}^m (1+x+\cdots+x^{b_j})\).

It is easily seen that the undirected power graph of a p-group G is a union of complete graphs of order p sharing the identity vertex if and only if G has exponent p. The following theorem describes all finite groups with this property.

Theorem 11.3. ([70]) The undirected power graph \(\mathcal{G}(G)\) is a union of complete graphs which share the identity element of G if and only if G is an EPPO-group and for any two distinct maximal cyclic subgroups A and B their intersection \(A \cap B\) is equal to \(\{e\}\).

Corollary 11.5. ([70]) If G is an EPO-group then the undirected power graph \(\mathcal{G}(G)\) is a union of complete graphs sharing the identity element of G.

Proposition 11.1. ([70]) A finite group G is an EPPO-group if and only if the vertices of every maximal clique of the undirected power graph \(\mathcal{G}(G)\) form a maximal cyclic subgroup of G.

12. Isomorphism

The following theorem shows that undirected power graphs can characterize all finite simple groups.

Theorem 12.1. ([70]) Let \(G_1\) be a finite group that is a simple group, or a cyclic group, or a symmetric group, or a dihedral group, or a generalised quaternion group. If \(G_2\) is a finite group such that \(\mathscr{G}(G_1) \cong \mathscr{G}(G_2)\), then \(G_1 \cong G_2\).

Theorem 12.2. ([23]) Let \(G_1\) and \(G_2\) be finite abelian groups such that \(\mathscr{G}(G_1) \cong \mathscr{G}(G_2)\). Then \(G_1 \cong G_2\).

It is explained in [23] that Theorem 12.2 does not generalize to infinite abelian groups. Indeed, let Cp^∞ be the group Qp/Z, where p is a prime and Q^p is the group of rational numbers with p-power denominators. Then G (Cp^∞) is a countably infinite complete graph, independent of the chosen prime.

It is also impossible to drop the condition that G be abelian from Theorem 12.2 either. Indeed, let G be a finite group of exponent 3, that is, satisfying x ³ = e for all x ∈ G. Then the undirected power graph G (G) consists of (|G| − 1)/2 triangles sharing the identity vertex. The elementary abelian group (the direct product of cyclic groups of order 3) has exponent 3. However, there are nonabelian groups of exponent 3 as well. The smallest one is the group of order 27 with presentation

\[G = \langle x, y \mid x^3 = y^3 = [x, y]^3 = 1 \rangle,\]

where [x, y] stands for the commutator x −1 y ⁻¹xy.

It is noted in [23] that a short calculation with GAP [85] and its package GRAPE [83] revealed that there are two pairs of groups of order 16 with isomorphic undirected power graphs, and two pairs of groups of order 27. As the order of the group increases, isomorphic power graphs become more common. For example, for order 32 there are one quadruple, two triples, and eight pairs. It is also possible to use Magma [19] for experimental verification of properties of this sort.

Theorem 12.3. ([70]) Let G be a finite group. The undirected power graph G (G) is bipartite if and only if G is an elementary abelian group of even order.

Theorem 12.4. ([23]) Let G¹ and G² be finite groups with −→^G (G1) ^∼= −→^G (G2). Then ^G1 and ^G2 have the same numbers of elements of each order.

Conjecture 2. ([23]) Let G¹ and G² be finite groups with G (G1) ∼= G (G2). Then G¹ and G² have the same numbers of elements of each order.

It is noted in [23] that this conjecture has been verified computationally using GAP [85] for all groups of order up to 511. The converse to the conjecture fails for groups of order 16.

Theorem 12.5. ([23]) The only finite group G for which Aut(G) = Aut(G (G)) is the Klein group Z² × Z2.

Theorem 12.6. ([22]) Two finite groups which have isomorphic undirected power graphs must have isomorphic directed power graphs.

Corollary 12.1. ([22]) Two finite groups whose undirected power graphs are isomorphic have the same numbers of elements of each order.

Theorem 12.7. ([22]) Let G be a finite group, and let S be the set of vertices of the undirected power graph G (G) which are joined to all other vertices. Suppose that |S| > 1. Then one of the following occurs:

• (a) G is cyclic of prime power order and S = G;
• (b) G is cyclic of order n that is not a power of a prime, and S consists of the identity and the generators of G, so that |S| = 1 + φ(n);

(c) G is generalised quaternion, and S contains the identity and the unique involution in G, so that |S| = 2.

13. Connected graphs

Let us define a binary relation % on S by a%b ⇔ a ^m = b ^m, for some m ∈ N.

Theorem 13.1. ([24]) Let S be a finite semigroup, and let a, b ∈ S, a 6= b. Then a and b are connected by a path in the graph G (S) if and only if a%b.

Corollary 13.1. ([24]) Let S be a finite semigroup. Then the connected components of the undirected power graph G (S) are precisely the sets C^e defined by

\[C_e = \{ x \in S \mid x \varrho e \} = \{ x \in S \mid \exists m \in \mathbb{N} : x^m = e \},\]

for all idempotents e in S.

A description of all idempotents of the semigroup (Zm, ·) of all integers modulo m with respect to multiplication is given in [24, §3]. In particular, it is shown that the graph G ((Zm, ·)) is disconnected for all m > 1 and that it is Eulerian if and only if n = 2.

Corollary 13.2. ([24]) Let S be a finite semigroup, then G (S) is connected if and only if S contains a single idempotent.

Proposition 13.1. ([24]) Let S be a semigroup such that G (S) is connected. Then S contains at most one idempotent.

Corollary 13.3. ([24]) Let S be a regular semigroup. If G (S) is connected, then S is a group.

Theorem 13.2. ([24]) Let G be a group. Then the undirected power graph G (G) is connected if and only if G is a torsion group.

The minimum number κ(D) of vertices of D which need to be removed to make the remaining graph disconnected is called the connectivity of D. If G is finite group, then we define

\[M(G) = \{ x \in G \mid x <_{\max} G \}.\]

For any element x of G, put r(x) = ∪y∈M(G)−hxⁱ(hxi ∩ hyi).

Theorem 13.3. ([70]) Let G be a finite group that is not a cyclic group. Then

\[\kappa(\mathscr{G}(G)) \le \min\{|r(x)| \mid \langle x \rangle <_{\max} G\}.\]

Theorem 13.4. ([27]) For any finite cyclic group Zn, the connectivity κ(G (Zn)) satisfies the following conditions:

• (i) κ(G (Zn)) = n − 1 when n = 1 or n = p ^m for a prime p and m ∈ N.
• (ii) κ(G (Zn)) = φ(n) + 1 when n is not a power of a prime number. The equality holds for n = pq, where p, q are distinct primes.

14. 2-connected graphs

A cut vertex in an undirected graph is a vertex whose removal increases the number of connected components of the graph. A graph is said to be 2-connected if it does not have a cut vertex.

Theorem 14.1. ([77]) Suppose that G is a p-group. The undirected power graph G (G) is 2 connected if and only if G is a cyclic group or generalized quaternion 2-group.

Theorem 14.2. ([77]) Let G be a nilpotent group. If G is not a p-group then the undirected power graph G (G) is 2-connected.

It is noted in [77] that the converse to Theorem 14.2 is not true. Indeed, the group G = Z⁵ ×S³ is not nilpotent, but its undirected power graph is 2-connected. Besides, the dihedral group D2p, where p is a prime, is a solvable group such that the undirected power graph G (D2p) is not 2-connected. Furthermore, the following proposition holds.

Proposition 14.1. ([77]) If A and B are groups of coprime orders such that A is cyclic of prime order, then the undirected power graph G (A × B) is 2-connected.

Question. ([77]) Does there exist a nonabelian simple group with a 2-connected power graph?

15. Diameter

The distance d(x, y) between vertices x and y of a connected graph D = (V, E) is the length of a shortest path connecting them. The maximum possible distance in D is called the diameter of D and is denoted by d(D). For example, in [10] a voltage assignment approach was used to construct large digraphs with small diameter.

The deletion of a single edge or vertex from a graph can change its diameter. Since the identity element of a group is adjacent to all other vertices of the undirected power graph of the group, one can delete any vertex, which is not the identity of the group, from the graph without changing its diameter. It would be interesting to determine when the same property holds for the identity vertex too. The following theorem gives a complete description of the structure of finite groups satisfying this property.

Theorem 15.1. ([76]) Let G be a finite group. Then d(G (G)) = d(G ∗ (G)) if and only if G is nilpotent and its Sylow subgroups are cyclic groups or generalized quaternion 2-groups.

Theorem 15.2. ([76]) Let G be a finite group such that d(G ∗ (G)) = 3. Then the Sylow subgroups of G are generalized quaternion 2-groups or cyclic and G is not nilpotent.

16. Girth

The girth of an undirected graph G is denoted by g(G) and is defined as the length of a shortest cycle in G.

Proposition 16.1. ([77]) The girth of undirected power graphs G (G) is equal to 3 if and only if G is not an elementary abelian 2-group. Besides, if G (G) is 2-connected then g(G (G) − e) = 3.

Proposition 16.2. ([77]) The undirected power graph of a finite group G is a tree if and only if G is an elementary abelian 2-group.

17. Combinatorial properties expressed as unavoidable regularities

Combinatorial properties of groups and semigroups defined in terms of all infinite subsets enjoying certain unavoidable regularities have been investigated by many authors, and a survey of this direction of research has been given in [33], (cf. [31, 32, 41, 53]).

The following combinatorial property of this sort has been defined in terms of directed power graphs in [43]. Let D = (V, E) be a directed graph. A semigroup S is said to be power Dsaturated if and only if, for every infinite subset T of S, the directed power graph of S has a subgraph isomorphic to D with all vertices in T.

A directed graph is said to be acyclic if it has no directed cycles.

Denote by T^∞ the transitive tournament with the vertex set N and the edge set E(T∞) = {(m, n) | m > n}.

If S is finite or if D is a null graph, then it is obvious that S is power D-saturated. Therefore the following theorems deal only with infinite groups or semigroups and with directed graphs which have edges.

Theorem 17.1. ([43]) Let D = (V, E) be a directed graph with E 6= ∅, and let G be an infinite group. Then G is power D-saturated if and only if G is a center-by-finite torsion group, the center Z(G) has a finite number of primary components, each primary component of Z(G) is finite or quasicyclic, the order of G/Z(G) is not divisible by p for each quasicyclic p-subgroup of G, and D is isomorphic to a subgraph of T∞.

For a skew field K, the set of all n × n matrices with entries in K is denoted by Mn(K). A matrix is said to be monomial if every row and column contains at most one nonzero entry. If G is a group, then the set of all n × n monomial matrices over G⁰ = G ∪ {0} forms a semigroup denoted by Mn(G). Thus a matrix semigroup is a subsemigroup of Mn(K) or Mn(G), for some n, K and G.

Theorem 17.2. ([47]) Let D = (V, E) be a directed graph with E 6= ∅, K a skew field, G a group, and let S be an infinite matrix semigroup in Mn(K) or in Mn(G). Then S is power D-saturated if and only if D is acyclic and all but a finite number of elements of S are contained in the union of a finite number of center-by-finite torsion groups Hⁱ , where i = 1, . . . , k, such that the center Z(Hi) of each Hⁱ has a finite number of primary components, each primary component of Z(Hi) is finite or quasicyclic, and the order of Hi/Z(Hi) is not divisible by p for each quasicyclic p-subgroup of Hi .

Theorem 17.3. ([44]) Let D = (V, E) be a finite graph with E 6= ∅, and let S be an infinite commutative semigroup. Then S is power D-saturated if and only if the following conditions hold:

• (i) D is acyclic,
• (ii) S is periodic,
• (iii) S has a finite number of idempotents,
• (iv) all but a finite number of elements of S belong to the union of all subgroups of S,

• (v) every subgroup of S has a finite number of primary components,
• (vi) for every prime p, each p-subgroup of S is either finite or quasicyclic.

Theorem 17.4. ([46]) Let D be a finite directed graph that is not null, and let S be an infinite semigroup. Then the following conditions are equivalent:

• (i) the directed power graph of S is D-saturated;
• (ii) D is acyclic and S ⁰ has a finite ideal series

\[0 = I_0 \subseteq I_1 \subseteq \dots \subseteq I_n = S^0 \tag{1}\]

where every infinite Rees quotient Ij/Ij−¹ is a Rees matrix semigroup that has a finite sandwich matrix with entries in a center-by-finite torsion group H^j such that each primary component of the center of H^j is finite or quasicyclic, the center of H^j has only a finite number of primary components, and the index of the center is not divisible by p for each quasicyclic p-subgroup of H^j .

18. Open questions

A Moore graph or digraph is a graph or digraph that meets the Moore bound or directed Moore bound, respectively. Let us refer to the survey [69] and articles [11, 12, 13, 14, 15, 16, 17, 81, 82, 88] for more information and examples of previous results pertaining to the Moore graphs and Moore bound.

Problem 2. Does there exist any undirected or directed power graph of a group or a semigroup, which is a Moore graph or digraph? Determine for which positive integers k there exist directed power graphs that are at distance k from achieving the optimality in terms of the Moore bound. Furthermore, for each positive integer k, describe all (a) groups and (b) semigroups whose directed or undirected power graphs are at distance k from achieving the Moore bound.

Let us refer to the survey [21] for previous results on graceful labellings.

Problem 3. Describe all groups and semigroups whose undirected power graphs have graceful labellings.

Edge-magic total labellings of graphs were considered, for example, in [86].

Problem 4. For each undirected power graph of a group or a semigroup, determine the number of edge-magic total labellings of the graph.

We refer to the survey [6] and papers [7, 8] for information on the edge antimagic labellings of graphs.

Problem 5. For each undirected power graph determine the number of edge antimagic labellings of the graph.

Let us refer to [9, 84] for preliminaries on super edge-antimagic labellings of graphs.

Problem 6. For each undirected power graph of a group or a semigroup, determine the number of super edge-antimagic labellings of the graph.

The readers are referred to [28] for preliminaries on group distance magic labellings and group distance antimagic labellings.

Problem 7. Investigate group distance magic labellings and group distance antimagic labellings of power graphs.

The readers are referred to [18] for background information on the Ramsey numbers of graphs.

Problem 8. Determine the Ramsey numbers of the undirected power graphs of all groups and semigroups.

Let us refer to [3, 4, 5] for more information concerning the face antimagic labellings of planar graphs.

Problem 9. For each planar undirected power graph of a group or a semigroup, determine the number of face antimagic labellings of the graph.

It is also essential to investigate the relations of power graphs and other important classes of graphs associated to groups and semigroups. One of the largest classes of graphs of this sort is that of Cayley graphs. Let G be a semigroup, and let S be a nonempty subset of G. As in [42], we say that the Cayley graph Cay(G, S) of G relative to S is defined as the directed graph with vertex set G and edge set E(S) consisting of those ordered pairs (x, y) such that sx = y for some s ∈ S. The set S is called the connection set of the Cayley graph Cay(G, S). The Cayley graph Cay(G, S) is also called the Cayley digraph. A Cayley graph Cay(G, S) is said to be undirected if, (u, v) ^{∈ E}(S) implies (v, u) ^{∈ E}(S). On the other hand, the underlying undirected graph ←−→Cay(G, S) of Cay(G, S) can be called the undirected Cayley graph of ^G relative to ^S.

Cayley graphs of semigroups have broad applications in versatile areas, as evidenced by the extensive bibliography given in the survey [48]. Cayley graphs of semigroups are closely related to automata theory, as explained in the monograph [37] and papers [35, 39, 45]. This is a very large topic, and so without trying to be complete we indicate only a few pertinent papers [20, 34, 38, 58, 59, 61, 62, 63, 64, 65, 66, 67, 68, 71, 72, 80, 81] just to illustrate.

Problem 10. Describe all directed and undirected power graphs of groups and semigroups that can be represented as Cayley graphs and, respectively, undirected Cayley graphs of groups or semigroups.

It would be also interesting to investigate the power graphs of ring constructions (cf. [36]). The most important ring constructions are the group rings, crossed products, group-graded rings and semigroup-graded rings (cf. [36, 40, 73, 74]). Let S be a semigroup. An associative ring R is said to be S-graded if R = L ^s∈^S R^s is a direct sum of additive groups Rs, and RsR^t ⊆ Rst, for all s, t ∈ S. The set H(R) = ∪s∈SR^s of homogeneous elements of R is a semigroup with respect to

multiplication. If G is a group and \(R = \bigoplus_{g \in G} R_g\) is G-graded, then R is called a group-graded ring. If e is the identity of the group G, then the component \(R_e\) is a subring of R. Group rings and crossed products are special cases of group-graded rings, and so the set H(R) is defined for these constructions too. Let us formulate the following general problems.

Problem 11. Let G be a group, R a ring, and let \(R[G] = \bigoplus_{g \in G} Rg\) be a group ring. Reduce various parameters of the graphs \(\overrightarrow{\mathcal{G}}(H(R[G]))\) and \(\mathcal{G}(H(R[G]))\) to the corresponding properties of the coefficient ring R and the group G.

Problem 12. Let G be a group with identity e, and let \(R = \bigoplus_{g \in G} R_g\) be

• (a) a crossed product, or
• (b) a group-graded ring.

Reduce various parameters of the graphs \(\overrightarrow{\mathcal{G}}(H(R))\) and \(\mathcal{G}(H(R))\) to the corresponding properties of the subring \(R_e\) and the group G.

Let D=(V,E) be a directed graph. The graph algebra \(\mathrm{Alg}(D)\) of D is the set \(V\cup\{0\}\) equipped with multiplication defined by the rule

\[xy = \begin{cases} x & \text{if } x, y \in V \text{ and } (x, y) \in E, \\ 0 & \text{otherwise.} \end{cases}\]

Let us refer to the monograph [37] and papers [39, 50, 51, 52] on graph algebras.

Problem 13. Describe all directed graphs whose graph algebras are power-associative.

The following problem makes sense for directed graphs and undirected graphs with appropriate adjustments.

Problem 14. For each power-associative graph algebra \(\operatorname{Alg}(D)\), determine the girth, diameter, connectivity, and the chromatic number of its directed power graph \(\overrightarrow{\mathcal{G}}(\operatorname{Alg}(D))\) and undirected power graph \(\mathcal{G}(\operatorname{Alg}(D))\).

Problem 15. Find conditions necessary and sufficient for the directed power graph \(\overrightarrow{\mathscr{G}}(\operatorname{Alg}(D))\) and undirected power graph \(\mathscr{G}(\operatorname{Alg}(D))\) to be planar.

Problem 16. Describe all directed graphs D such that the graph algebra Alg(D) is power-associative and its undirected power graph has a graceful labelling.

Acknowledgements

The authors are grateful to Seyed Ashrafi, Sriparna Chattopadhyay, Shamik Ghosh, Ulrich Knauer, Pratima Panigrahi, Gholam Reza Pourgholi and Sanming Zhou for pre-publication versions of their papers. The authors are grateful to Brian Curtin, Gholam Reza Pourgholi and Igor Shparlinski for comments and lists of typographical corrections to the manuscript. The authors would like to thank two referees for helpful reports.

References

• [1] J. Abawajy and A. V. Kelarev, Classification systems based on combinatorial semigroups, Semigroup Forum, 86 (2013), 603–612.
• [2] H. Amiri, S. M. Jafarian Amiri and I. M. Isaacs, Sums of element orders in finite groups, Comm. Algebra, 37 (2009), 2978–2980.
• [3] M. Baca, E. T. Baskoro, Y. M. Cholily, S. Jendrok, Y. Lin, M. Miller, J. Ryan, R. Simanjuntak, Slamin and K. A. Sugeng, Conjectures and open problems on face antimagic evaluations of graphs, Journal of Indonesian Math. Society (MIHMI), 11 (2005), 175–192.
• [4] M. Baca, E. T. Baskoro, S. Jendrok and M. Miller, Antimagic labelings of hexagonal planar maps, Utilitas Mathematica, 66 (2004), 231–238.
• [5] M. Baca, E. T. Baskoro and M. Miller, Antimagic valuations for the special class of plane graphs, Lecture Notes in Computer Science, 3330 (2005), 58-64.
• [6] M. Baca, E. T. Baskoro, M. Miller, J. Ryan, R. Simanjuntak and K. A. Sugeng, Survey of edge antimagic labelings of graphs, Journal of Indonesian Math. Society (MIHMI), 12 (2006), pp. 113-130,
• [7] M. Baca and L. Brankovic, Edge-antimagicness for a class of disconnected graphs, Ars Combinatoria, 97A (2010), 145–152.
• [8] M. Baca, L. Brankovic, M. Lascsakova, O. Phanalasy and A. Semanicova-Fenovciova, On d-antimagic labelings of plane graphs, Electronic Journal of Graph Theory and Applications, 1 (2013), 28–39.
• [9] M. Baca and M. Miller, Super Edge-Antimagic Graphs: A Wealth of Problems and Some Solutions, Brown Walker Press, 2008.
• [10] E. T. Baskoro, L. Brankovic, M. Miller, J. Plesnik, J. Ryan and J. Sir ˇ an, Large digraphs with ´ small diameter: A voltage assignment approach, Journal of Combinatorial Mathematics and Combinatorial Computing, 24 (1997), 161–176.
• [11] E. T. Baskoro, Y. M. Cholily and M. Miller, Structure of selfrepeat cycles in almost Moore digraphs with selfrepeats and diameter 3, Bulletin of the Institute of Combinatorics and its Applications, 46 (2006), 99-109.
• [12] E. T. Baskoro, Y. M. Cholily and M. Miller, Enumeration of vertex orders of almost Moore digraphs with selfrepeats, Discrete Mathematics, 308 (2008), 123–128.
• [13] E. T. Baskoro, M. Miller and J. Plesnik, On the structure of digraphs with order close to the Moore bound, Graphs and Combinatorics, 14 (1998), 109–119.
• [14] E. T. Baskoro, M. Miller and J. Plesnik, Further results on almost Moore digraphs, Ars Combinatoria, 56 (2000), 43–63.

• [15] E. T. Baskoro, M. Miller, J. Plesnik and S. Znam, Digraphs of degree 3 close to Moore bound, Journal of Graph Theory, 20 (1995), 339–349.
• [16] E. T. Baskoro, M. Miller and J. Sir ˇ an, A note on almost Moore digraphs of degree three, ´ Acta Mathematica Universitatis Comenianae, LXVI (1997).
• [17] E. T. Baskoro, M. Miller, J. Sir ˇ an and M. Sutton, Complete characterization of almost Moore ´ digraphs of degree three, Journal of Graph Theory, 48 (2005), 112–126.
• [18] E. T. Baskoro, Surahmat, S. M. Nababan and M. Miller, On Ramsey numbers for trees versus wheels of five or six vertices, Graphs and Combinatorics, 18 (2002), 717–721.
• [19] W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput., 24 (1997), 235–265.
• [20] L. Brankovic, M. Miller, J. Plesnik, J. Ryan and J. Siran, A note on constructing large Cayley graphs of given degree and diameter by voltage assignment, Electronic J. Combinatorics, 5 (1998), 147–158.
• [21] L. Brankovic and I. M. Wanless, Graceful labelling: state of the art, applications and future directions, Mathematics in Computer Science, 5 (2011), 11–20.
• [22] P. J. Cameron, The power graph of a finite group, II, Journal of Group Theory, 13 (2010), 779–783.
• [23] P. J. Cameron and S. Ghosh, The power graph of a finite group, Discrete Mathematics, 311 (2011), 1220–1222.
• [24] I. Chakrabarty, S. Ghosh and M. K. Sen, Undirected power graphs of semigroups, Semigroup Forum, 78 (2009), 410–426.
• [25] G. Chartland and L. Lesniak, Graphs and Digraphs, Chapman & Hall, London, 1996.
• [26] S. Chattopadhyay and P. Panigrahi, Power graphs of finite groups of even order, Communications in Computer and Information Science, 283 (2012), 62–67.
• [27] S. Chattopadhyay and P. Panigrahi, Connectivity and Planarity of Power Graphs of Finite Cyclic Dihedral and Dicyclic Groups, Algebra and Discrete Mathematics, accepted.
• [28] S. Cichacz, D. Froncek, K. Sugeng and Sanming Zhou, Group distance magic and antimagic graphs, arXiv1309.7454v1, 2013, 1–17.
• [29] M. Hazewinkel, Magma, Encyclopedia of Mathematics, Springer, 2001.
• [30] J. M. Howie, Fundamentals of Semigroup Theory, Clarendon Press, Oxford, 1995.
• [31] J. Justin and A. V. Kelarev, Factorizations of infinite sequences in semigroups, Annali di Matematica Pura ed Applicata, 174 (1998), 87–96.

• [32] A. V. Kelarev, Combinatorial properties and homomorphisms of semigroups, International Journal of Algebra and Computation, 4 (1994), 443–450.
• [33] A. V. Kelarev, Combinatorial properties of sequences in groups and semigroups, Discrete Mathematics and Theoretical Computer Science, 1996, 289–298.
• [34] A. V. Kelarev, On undirected Cayley graphs, Australasian J. Combinatorics, 25 (2002), 73– 78.
• [35] A. V. Kelarev, Labelled Cayley graphs and minimal automata, Australasian J. Combinatorics, 30 (2004), 95–101.
• [36] A. V. Kelarev, Ring Constructions and Applications, World Scientific, River Edge, NJ, 2002.
• [37] A. V. Kelarev, Graph Algebras and Automata, Marcel Dekker, New York, 2003.
• [38] A. V. Kelarev, On Cayley graphs of inverse semigroups, Semigroup Forum, 72 (2006), 411– 418.
• [39] A. V. Kelarev, M. Miller and O. V. Sokratova, Languages recognized by two-sided automata of graphs, Proc. Estonian Akademy of Science, 54 (2005), 46–54.
• [40] A. V. Kelarev and D. S. Passman, A description of incidence rings of group automata, Contemporary Mathematics, 456 (2008), 27–33.
• [41] A. V. Kelarev and G. Pirillo, A note on rewritable products in groups and semigroups, Bollettino Unione Mat. Italiano, 11-A (1997), 667–670.
• [42] A. V. Kelarev and C.E. Praeger, On transitive Cayley graphs of groups and semigroups, European J. Combinatorics, 24 (2003), 59–72.
• [43] A. V. Kelarev and S. J. Quinn, A combinatorial property and power graphs of groups, Contrib. General Algebra, 12 (2000), 229–235.
• [44] A. V. Kelarev and S. J. Quinn, Directed graphs and combinatorial properties of semigroups, J. Algebra, 251 (2002), 16–26.
• [45] A. V. Kelarev and S. J. Quinn, A combinatorial property and Cayley graphs of semigroups, Semigroup Forum, 66 (2003), 89–96.
• [46] A. V. Kelarev and S. J. Quinn, A combinatorial property and power graphs of semigroups, Comment. Math. Univ. Carolinae, 45 (2004), 1–7.
• [47] A. V. Kelarev, S. J. Quinn and R. Smolikova, Power graphs and semigroups of matrices, Bull. Austral. Math. Soc., 63 (2001), 341–344.
• [48] A. Kelarev, J. Ryan and J. Yearwood, Cayley graphs as classifiers for data mining: The influence of asymmetries, Discrete Mathematics, 309 (2009), 5360–5369.

• [49] A. Kelarev, J. Ryan and J. Yearwood, An algorithm for the optimization of multiple classifiers in data mining based on graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, 71 (2009), 65–86.
• [50] A. V. Kelarev and O. V. Sokratova, Directed graphs and syntactic algebras of tree languages, J. Automata, Languages & Combinatorics, 6 (2001), 305–311.
• [51] A. V. Kelarev and O. V. Sokratova, Languages recognized by a class of finite automata, Acta Cybernetica, 15 (2001), 45–52.
• [52] A. V. Kelarev and O. V. Sokratova, On congruences of automata defined by directed graphs, Theoretical Computer Science, 301 (2003), 31–43.
• [53] A. V. Kelarev and P. G. Trotter, A combinatorial property of languages and monoids, Proceedings of the International Conference Words, Languages and Combinatorics III, Kyoto, Japan, 2003, 228–239.
• [54] A. V. Kelarev, P. W. Watters and J. L. Yearwood, Rees matrix constructions for clustering of data, J. Aust. Math. Soc., 87 (2009), 377–393.
• [55] A. V. Kelarev, J. L. Yearwood and M. A. Mammadov, A formula for multiple classifiers in data mining based on Brandt semigroups, Semigroup Forum, 78 (2009), 293–309.
• [56] A. V. Kelarev, J. L. Yearwood and P. A. Watters, Optimization of classifiers for data mining based on combinatorial semigroups, Semigroup Forum, 82 (2011), 242–251.
• [57] A. V. Kelarev, J. L. Yearwood and Lifang Zi, Optimal Rees matrix constructions for analysis of data, J. Aust. Math. Soc., 92 (2012), 357–366.
• [58] B. Khosravi and B. Khosravi, On Cayley graphs of semilattices of semigroups, Semigroup Forum, 86 (2013), 114–132.
• [59] B. Khosravi and M. Mahmoudi, On Cayley graphs of rectangular groups, Discrete Mathematics, 310 (2010), 804–811.
• [60] U. Knauer, Algebraic Graph Theory, De Gruyter, Berlin, 2011.
• [61] S. Lakshmivarahan, J.-S. Jwo and S. K. Dhall, Symmetry in interconnection networks based on Cayley graphs of permutation groups: a survey, Parallel Computing, 19 (1993), 361–407.
• [62] C. H. Li, On isomorphisms of finite Cayley graphs a survey, Discrete Mathematics, 256 (2002), 301–334.
• [63] C. H. Li and C. E. Praeger, On the isomorphism problem for finite Cayley graphs of bounded valency, European J. Combinatorics, 20 (1999), 279–292.
• [64] X. Liu and S. Zhou, Spectral properties of unitary Cayley graphs of finite commutative rings, Electronic Journal of Combinatorics, 19 (2012), 1–19.

• [65] M. E. Lladser, P. Potocnik, J. Sir ˇ an and M. C. Wilson, Random Cayley digraphs of diameter ´ 2 and given degree, Discrete Math. Theor. Comput. Sci., 14 (2012), 83–90.
• [66] E. Loz, M. Macaj, M. Miller, Siagiov ˇ a, J. ´ Sir ˇ an and J. Tomanov ´ a, Small vertex-transitive and ´ Cayley graphs of girth six and given degree: an algebraic approach, J. Graph Theory, 68 (2011), 265–284.
• [67] B. D. McKay and C. E. Praeger, Vertex-transitive graphs which are not Cayley graphs, I, J. Austr. Math. Soc. Series A, 56 (1994) 53-63.
• [68] B. D. McKay and C. E. Praeger, Vertex-transitive graphs which are not Cayley graphs, II, J. Graph Theory, 22 (1996), 321–334.
• [69] M. Miller and J. Sir ˇ an, Moore graphs and beyond: A survey of the degree/diameter problem, ´ Electronic J. Combinatorics, Dynamic Survey, DS20, 2013, 92pp.
• [70] M. Mirzargar, A. R. Ashrafi and M. J. Nadjafi-Arani, On the power graph of a finite group, Filomat, 26 (2012) (6), 1201–1208.
• [71] S. Panma, U. Knauer and S. Arworn, On transitive Cayley graphs of strong semilattices of right (left) groups, Discrete Mathematics, 309 (2009), 5393–5403.
• [72] S. Panma, N. Na Chiangmai, U. Knauer and S. Arworn, Characterizations of Clifford semigroup digraphs, Discrete Mathematics, 306 (2006), 1247–1252.
• [73] D. S. Passman, The algebraic structure of group rings, Wiley-Interscience, New York, London, Sydney, 1977.
• [74] D. S. Passman, Infinite crossed products, Academic Press, Boston, MA, 1989.
• [75] G. R. Pourgholi, A note on the power graph of a finite group, Journal of Algebraic Combinatorics, accepted.
• [76] G. R. Pourgholi and H. Yousefi-Azari, On the 2-connected power graphs of finite groups, Australiasian J. Combinatorics, accepted.
• [77] G. R. Pourgholi, H. Yousefi-Azari and A. R. Ashrafi, The undirected power graph of a finite group, Bull. Malaysian Math. Sci. Soc., accepted.
• [78] N. R. Reilly, Introduction to Applied Algebraic Systems, Oxford University Press, Oxford, 2010.
• [79] D. J. S. Robinson, A Course in the Theory of Groups, Springer, New-York, Berlin, 1982.
• [80] J. Siagiov ˇ a and J. ´ Sir ˇ an, A note on large Cayley graphs of diameter two and given degree, ´ Discrete Mathematics, 305 (2005), 379–382.

• [81] J. Siagiov ˇ a and J. ´ Sir ˇ an, Approaching the Moore bound for diameter two by Cayley graphs, ´ Journal of Combinatorial Theory Ser. B, 102 (2012), 470–473.
• [82] Slamin, E. T. Baskoro and M. Miller, Diregularity of digraphs of out-degree three and order two less than Moore bound, Proceedings of the Twelfth Australasian Workshop on Combinatorial Algorithms, AWOCA 2001, Bandung, Indonesia, 2001, pp.164-173.
• [83] L. H. Soicher, GRAPE: a system for computing with graphs and groups, Discrete Mathematics and Theoretical Computer Science, 1993, 287–291, http://www.maths.qmul.ac.uk/˜leonard/grape/
• [84] K. A. Sugeng, M. Miller, J. Ryan, Y. M. Cholily and E. T. Baskoro, Expanding super (a,d) edge-antimagic total labelings, Journal of Combinatorial Mathematics and Combinatorial Computing, in press.
• [85] The GAP Group, GAP Groups, Algorithms, and Programming, Version 4.6.5; 2013, http://www.gap-system.org/
• [86] W. D. Wallis, E. T. Baskoro, M. Miller and Slamin, Edge-magic total labelings, Australasian J. Combinatorics, 22 (2000), 177–190.
• [87] E. W. Weisstein, Groupoid, MathWorld, http://mathworld.wolfram.com/Groupoid.html
• [88] Sanming Zhou, Unitary graphs, J. Graph Theory, in press, doi:10.1002/jgt.21721.