On the power graph of the direct product of two groups

arXiv:1606.07258v1 [math.CO] 23 Jun 2016

A. K. Bhuniya and Sajal Kumar Mukherjee

Department of Mathematics, Visva-Bharati, Santiniketan-731235, India.
anjankbhuniya@gmail.com, shyamal.sajalmukherjee@gmail.com
Abstract
The power graph P (G) of a finite group G is the graph with vertex set G and two distinct
vertices are adjacent if either of them is a power of the other. Here we show that the power graph
P (G1 × G2 ) of the direct product of two groups G1 and G2 is not isomorphic to either of the
direct, cartesian and normal product of their power graphs P (G1 ) and P (G2 ). A new product
of graphs, namely generalized product, has been introduced and we prove that the power graph
P (G1 × G2 ) is isomorphic to a generalized product of P (G1 ) and P (G2 ).

Keywords: finite groups; direct product; power graphs; product of graphs; isomorphism.
AMS Subject Classifications: 05C25

1

Introduction

The directed power graph of a semigroup was defined by Kelarev and Quinn [6]. Then Chakraborty
et. al [3] defined the undirected power graph P (S) of a semigroup S as the graph with vertex set S
and two distinct vertices a and b are adjacent if either am = b or bn = a for some m, n ∈ N. There
are many articles associating group theoretic behavior of G and the graph theoretic properties of
P (G). We refer to the survey [1] for an account of the development on the power graph of groups
and semigroups. Success attained by the researchers in this direction influenced others to generalize
power graph of groups to strong power graph [8], deleted power graph P ∗ (G) [7], enhanced power
graph [2].
Here we investigate relationship of P (G1 ×G2 ) with P (G1) and P (G2 ). There are many standard
products of graphs, already defined, namely, direct product, cartesian product, normal product etc.
Here we show that, in general, P (G1 × G2 ) is not isomorphic to either of these products of P (G1) and
P (G2 ). So we introduce a new product of two graphs Γ1 and Γ2 , which we call generalized product
1

of Γ1 and Γ2 . Reason behind such naming is that each of the cartesian, direct and normal products
is a special case of the generalized product of two graphs.
Our main theorem states that P (G1 × G2 ) is isomorphic to a generalized product of the power
graphs P (G1) and P (G2).

2

Main result

We refer to [4] and [9] for the notions on graph theory and to [5] for group theoretic background.
S
Throughout this article N denotes the set of natural numbers and Z♯ = N {0}.
Let us recall different standard notions of products of graphs.
Definition 2.1. Let Γ1 and Γ2 be two graphs.
(i) The direct product Γ1 × Γ2 of Γ1 and Γ2 is defined as follows:
V (Γ1 × Γ2 ) = V (Γ1 ) × V (Γ2 ) and (g1 , g2) ∼ (g´1 , g´2 ) if and only if g1 ∼ g´1 and g2 ∼ g´2 .
(ii) The cartesian product Γ1 ⊠ Γ2 of Γ1 and Γ2 is defined as follows:
V (Γ1 ⊠ Γ2 ) = V (Γ1 ) × V (Γ2 ) and (g1 , g2 ) ∼ (g´1 , g´2 ) if and only if either g1 = g´1 and g2 ∼ g´2 or
g1 ∼ g´1 and g2 = g´2 .
(iii) The normal product Γ1 ∗ Γ2 of Γ1 and Γ2 is defined as follows:
V (Γ1 ∗ Γ2 ) = V (Γ1 ) × V (Γ2 ) and (g1 , g2 ) ∼ (g´1 , g´2 ) if and only if either g1 ∼ g´1 and g2 ∼ g´2 or
g1 = g´1 and g2 ∼ g´2 or g1 ∼ g´1 and g2 = g´2 .
Now we show that neither of these notions of product of graphs is enough to catch the relationship
of P (G1 × G2 ) with P (G1 ) and P (G2 ).
Proposition 2.2. Let G1 and G2 be two nontrivial finite groups. Then P (G1 ×G2 ) is not isomorphic
to P (G1 ) ⊠ P (G2 ).
Proof. Suppose, on the contrary that the two graphs, stated in the theorem are isomorphic. Let
ei be the identity element of the group Gi . Let g1 , g2 be two nonidentity elements of G1 and G2
respectively. Then (e1 , e2 ) is not adjacent to (g1 , g2 ) in P (G1) ⊠ P (G2 ), whereas (eG1 , eG2 ) ∼ (g1 , g2 )
in P (G1 × G2 ). A contradiction.

2

Consider G1 = G2 = Z2 . Then P (Z2 × Z2 ) has precisely three edges, each edge emanating
from the identity of Z2 × Z2 and connects the remaining three vertices, whereas P (Z2 ) ∗ P (Z2) is the
complete graph K4 and P (Z2 ) × P (Z2 ) is a graph with precisely two edges.
Thus we show that P (G1 × G2 ) is neither isomorphic to the direct product nor to the normal
product of P (G1) and P (G2), in general.
So we need to introduce another product of graphs to uncover the relationship of the power
graphs P (G1) and P (G2) with P (G1 × G2 ) for any two groups G1 and G2 .
Before going into technical details, note the following fact. Let G be a finite group and a, b ∈ G.
Suppose that a ∼ b in P (G). It is easy to observe that if n is the smallest positive integer such
that an = b, then {m ∈ N : am = b} is the arithmetic progression with initial term n and common
difference o(a).
For any two integers a and d, we denote the arithmetic progression with initial term a and
common difference d by AP (a, d).
Let Γ be a graph. Then by a generalization on Γ we mean a function W : A(Γ)

S

△ → Z♯ × Z♯ ,

where A(Γ) is the arc set of Γ and △ = {(v, v) : v is a vertex of Γ}.
Definition 2.3. Let (Γ1 , W1 ) and (Γ2 , W2 ) be two graphs equipped with two generalizations W1 , W2
respectively. Then the generalized product Γ1

W1

×W2 Γ2 is a graph with vertex set V (Γ1 ) × V (Γ2 ) and

(g1 , g2 ) ∼ (g´1 , g´2) if and only if the following two conditions hold simultaneously:
(i) (g1 , g2 ) 6= (g´1 , g´2 ) and
(ii) AP (W1 (g1 , g´1 )) ∩ AP (W2 (g2 , g´2 )) ∩ N 6= φ or AP (W1 (g´1 , g1 )) ∩ AP (W2 (g´2 , g2 )) ∩ N 6= φ.
If no question of ambiguity arise, then we denote a generalized direct product of two graphs Γ1
and Γ2 by Γ1 ×W Γ2 .
The following result justifies the name ‘generalized product’.
Theorem 2.4. Each of the direct, cartesian and normal products is a generalized product.
Proof. Let Γ1 and Γ2 be two graphs.
(i) Consider the generalizations W1 of Γ1 defined by:
W1 (x, y) = (1, 1) if x 6= y
= (0, 0) if x = y.
and W2 of Γ2 defined similarly. Then it is easy to verify that Γ1 ×W Γ2 = Γ1 × Γ2 .
3

(ii) Consider the generalizations W1 of Γ1 defined by:
W1 (x, y) = (1, 0) if x 6= y
= (1, 1) if x = y.
and W2 of Γ2 defined by:
W1 (x, y) = (2, 0) if x 6= y
= (1, 1) if x = y.
Then Γ1 ×W Γ2 = Γ1 ⊠ Γ2 .
(iii) Consider the generalizations W1 of Γ1 defined by:
W1 (x, y) = (1, 0) if x 6= y
= (1, 1) if x = y.
and W2 of Γ2 defined similarly. Then Γ1 ×W Γ2 = Γ1 ∗ Γ2 .

Now, we prove our main theorem.
Theorem 2.5. For two groups G1 and G2 , P (G1 × G2 ) and P (G1) ×W P (G2) are isomorphic for
some choice of generalizations W1 and W2 of P (G1 ) and P (G2 ) respectively.
Proof. Let us first specify the choice of the generalizations of P (G1 ) and P (G2). We consider the
generalization W1 of P (G1 ) defined by:
W1 (a, b) = (t, o(a)) if t is the smallest positive integer such that at = b
= (0, 0) otherwise.
and the generalization W2 of P (G2 ) defined similarly.
Let (g1 , g2 ) ∼ (g´1 , g´2 ) in P (G1 × G2 ). Then either (g1 , g2 )m = (g´1 , g´2 ) or (g´1 , g´2 )n = (g1 , g2 ) for
some m, n ∈ N. If (g1 , g2)m = (g´1 , g´2 ) then g1m = g´1 implies that m ∈ AP (t, o(g1)) where t is the
smallest positive integer for which g1t = g´1 . Hence m ∈ AP (W1 (g1 , g´1 )). Similarly g2m = g´2 implies
that m ∈ AP (W2 (g2 , g´2 )). Thus AP (W1 (g1 , g´1 )) ∩ AP (W2 (g2 , g´2 )) ∩ N 6= φ and so (g1 , g2 ) ∼ (g´1 , g´2 )
in P (G1 ) ×W P (G2 ). If (g´1 , g´2 )n = (g1 , g2 ) then AP (W1 (g´1 ), g1 ) ∩ AP (W2 (g´2 ), g2 ) ∩ N 6= φ and so
(g1 , g2 ) ∼ (g´1 , g´2) in P (G1) ×W P (G2).
Conversely, let (g1 , g2 ) ∼ (g´1 , g´2) in P (G1 ) ×W P (G2 ). If m ∈ AP (W1 (g1 , g´1 )) ∩ AP (W2 (g2 , g´2 )) ∩
N 6= φ, then (g1 , g2 )m = (g´1 , g´2 ) and hence (g1 , g2 ) ∼ (g´1 , g´2 ) in P (G1 × G2 ). Similar is the other
case.
4

Acknowledgement: The second author is partially supported by CSIR-JRF grant.

References
[1] J. Abawajy, A. V. Kelarev and M. Chowdhury, Power graphs: A survey, Electron. J. Graph
Theory Appl, 1(2013), 125-147.
[2] G. Aalipour, S. Akbari, P. J. Cameron, R. Nikandish, F. Shaveisi, On the structure of the power
graphs and the enhanced power graphs of a group, arXiv: 1603.04337v1(2016)[math. CO].
[3] I. Chakrabarty, S. Ghosh and M. K. Sen, Undirected power graphs of semigroups, Semigroup
Forum , 78(2009), 410-426.
[4] C. Godsil and G. Royle, Algebraic Graph Theory, Springer-Verlag, New York Inc, 2001.
[5] T. W. Hungerford, Algebra, Graduate Text in Mathematics 73, Springer-Verlag, New York(NY),
(1974).
[6] A. V. Kelarev and S. J. Quinn, A combinatorial property and power graphs of groups, Contributions to General Algebra, 12(Heyn, Klagenfurt, 2000), 229-235.
[7] A. R. Moghaddanfar, S. Rahbariyan, W. J. Shi, Certain properties of the power graph associated
with a finite group, arXiv: 1310.2032v1(2013)[math. GR].
[8] G. Singh and K. Manilal, Some generalities on power graphs and strong power graphs, Int. J.
Contemp. Math Sciences, 5(55)(2010), 2723-2730.
[9] D. B. West, Introduction to Graph theory, 2nd ed., Pearson education, 2001.

5

