Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 5s (2024) 

 

197 
https://internationalpubls.com 

The Structure of Generalized Cayley Graph When 𝑪𝒂𝒚(𝑮, 𝑺) =

 𝑷𝟐 × 𝑷𝟐 and 𝑷𝟐 × 𝑪𝟑 

 

Ayat A. Neamah 

Department of Mathematics, Al-Nahrain University, Baψhdad, Iraq 

ayatneamah@nahrainuniv.edu.iq 

 

Article History: 

Received: 15-05-2024 

Revised: 24-06-2024 

Accepted: 03-07-2024 

Abstract 

This work aims to present the generalized Cayley graph and identify its structure in a 

few specific scenarios. Assume that Ψ is a finite-group and that S is a non-empty 

subset of Ψ. 

  𝑒 ∉ 𝑆 and . As a result, the vertices of the Cayley graph Cay (Ψ,S) are all 

members of Ψ, and two nearby vertices, x and y, are only adjacent if  𝑥𝑦−1 ∈ 𝑆. The 

given generalized Cayley graph is defined as 𝐶𝑎𝑦𝑚 This is a graph whose vertex 

set is made up of every column matrix 𝑋𝑚 It has two vertices and all of its components 

in Ψ. 𝑋𝑚 and 𝑌𝑚 are adjacent ↔ , where 𝑌𝑚
−1 is a column 

matrix in which ∀ entry correlates to an associated element's inverse.  and 𝑀(𝑆) 

is a m×m matrix where every entry is in S ,  is the opposite of    and 

. In this study, we assign the structure of the new graph and highlight  some of 

its fundamental aspects 𝐶𝑎𝑦𝑚(𝐺, 𝑆) when 𝐶𝑎𝑦(𝐺, 𝑆) is the 𝑃2 × 𝑃2 and 𝑃2 × 𝐶3. 

Keywords: Cayley Graph, Algebraic graph theory etc. 

 

Introduction. 

Algebraic graph theory has emerged as a prominent mathematical topic of interest to specialists in the 

domains of algebra and graph theory in recent years. Algebraic graph theory states that every graph 

may be associated with a group, ring, module, or any other algebraic structure. An algebraic graph that 

is particularly interesting is the Cayley graph for a group and related subset. In 1878, Arthur Cayley 

created the Cayley graph to provide clarification on the concept of abstract groups, which at the time 

were created by a group of generators. A graph with a group encoded is called a Cayley graph. 

Assuming Ψ is a group and S is its inverse closed subset, we may conclude that e∉S. As a result, the 

Cayley graph Cay(Ψ,S) is an undirected simpl-graph whose vertex set is made up of all of Ψ's 

members, and x is next to y only if  𝑥𝑦−1 ∈ 𝑆. We note that 𝐶𝑎𝑦  is a simple 𝑟 −regular graph 

and it depends on to set 𝑆 of the group. Also, 𝐶𝑎𝑦 is connected↔ 𝑆 is a generating set of 𝐺.    A 

new definition of the generalized Cayley graph, called Caym (Ψ,S), was recently provided by Erfanian 

in [4]. This new definition uses column m×1 matrices and is a novel extension of the standard Cay(

). The generalized Cayley graph, represented as Cay_m , is an undirected simple graph with 

two vertices and a vertex set made up of all m×1 matrices, where x_i∈G,1≤i≤m, for each positive 

integer m≥1   𝑋 = [𝑥1, 𝑥2, … , 𝑥𝑚]𝑡  and 𝑌 = [𝑦1, 𝑦2, … , 𝑦𝑚]𝑡 are contiguous only in the event that X(Y) 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 5s (2024) 

 

198 
https://internationalpubls.com 

)t∈M(S). Since it is obvious that the standard Cayley graph Cay(Ψ,S) exists if m=1, we refer to this as 

the generalized Cayley graph. In this work, we consistently assume that S^(-1)⊆S, e∉S, and S is a 

entertain set of G. Cay(G,S) is therefore a connected graph in this case.  

In this paper, we focus on the Cartesian product of two graphs in order to determine the generalized 

Cayley graph.  𝐶𝑎𝑦(𝐺, 𝑆) = 𝑃2 × 𝑃2 and 𝐶𝑎𝑦(𝐺, 𝑆) = 𝑃2 × 𝐶3.  

Binary operations create a new graph from two initial graphs 𝐺, 𝐻 , such as graph union, 

Cartesian graph product, Corona graph product, and generalized corona product. Here we define these 

graph operations. 

Definition 1. Assuming  Ψ and H represent two graphs. Following that, the graph represented by 

Ψ∪H, which is the union of Ψ and H  𝑉(𝐺 ∪ 𝐻) = 𝑉(𝐺) ∪ 𝑉(𝐻) and 𝐸(𝐺 ∪ 𝐻) = 𝐸(𝐺) ∪ 𝐸(𝐻). 

Definition 2. The graph denoted by Ψ×H is the Cartesian product of Ψ and H, with V(G)×V(H) as its 

vertex set. There are two vertices  (𝑔, ℎ), (𝑔′, ℎ′) are next to each other if (gg'∈ G┧ and ├ 

h=h^'∈E(H)) or (g=g' ┧ and ├ hh'∈E(H)). Therefore, E(G×H)={(g,h)(g',h' )│g=g',hh'∈E(H) or gg'∈ 

E(G),├ h=h' ) } and V(G×H)={(g,h)├|g∈┤V(G),h∈V (H)}. Factors of G×H are represented by the 

graph G,H. 
Definition 3. Assuming 𝜓 and H are graphs, one may derive the Corona product of Ψ and H, 

represented as Ψ∘H, by linking each vertex of the i-th copy of H to the i-th vertex of G, where 

, using one copy of Ψ and |V(G)| The functioning of copies of H. Corona product is non-

commutative.  . 

Lemma 4. Let 𝑋 = [𝜛1, 𝜛2, … , 𝜛𝑚]𝑡   and 𝑌 = [𝑦1, 𝑦2, … , 𝑦𝑚]𝑡  be two arbitrary vertices of 

𝐶𝑎𝑦𝑚(𝐺, 𝑆)  where 𝑥𝑖  and 𝑦𝑗  are in 𝐺  for all 𝑖, 𝑗 ∈ {1,2, . . . , 𝑚}, then 𝑋  and 𝑌  are adjacent ↔ 𝑥𝑖  is 

adjacent to 𝑦𝑗 in 𝐶𝑎𝑦(𝐺, 𝑆) ∀l 𝑖, 𝑗 ∈ {1,2, . . . , 𝑚}.  

Here, we find the generalized Cayley graph when 𝐶𝑎𝑦(𝐺, 𝑆) is the Cartesian products 𝑃2 × 𝑃2 and 

𝑃2 × 𝐶3.  

Lemma 5. Let 𝐶𝑎𝑦(𝐺, 𝑆) = 𝑃2 × 𝑃2, then 𝐶𝑎𝑦2(𝐺, 𝑆) = 𝐾4,4 ∪ 8𝑃1. 

Proof: Suppose that  𝐺1 = 𝑃2  with vertex set {𝑥1, 𝑥2}  and 𝐺2 = 𝑃2  with vertex set {𝑥3, 𝑥4}  and 

𝐶𝑎𝑦(𝐺, 𝑆) = 𝑃2 × 𝑃2. So, 𝐶𝑎𝑦(𝐺, 𝑆) is a cycle of length 4 and its vertex set is  

𝑉(𝐶𝑎𝑦(𝐺, 𝑆)) = {(𝑥1, 𝑥3), (𝑥1, 𝑥4), (𝑥2, 𝑥3), (𝑥2, 𝑥4)}  

and the set of four edges {(𝑥1, 𝑥3)(𝑥1, 𝑥4), (𝑥1, 𝑥3)(𝑥2, 𝑥3), (𝑥2, 𝑥3)(𝑥2, 𝑥4), (𝑥2, 𝑥4)(𝑥1, 𝑥4)} 

Since the Cayley graph is a cycle (𝑥1, 𝑥3) −  (𝑥1, 𝑥4) − (𝑥2, 𝑥4) −  (𝑥2, 𝑥3) − (𝑥1, 𝑥3). Then, we have 

42 = 16 vertices in  𝐶𝑎𝑦2(𝐺, 𝑆) and 𝑉(𝐶𝑎𝑦2(𝐺, 𝑆)) = {[
𝑎
𝑏

] |𝑎, 𝑏 ∈ 𝑉(𝐶𝑎𝑦(𝐺, 𝑆))}  

 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 5s (2024) 

 

199 
https://internationalpubls.com 

 

Consequently. Every vertex in set A is obviously adjacent to every vertex in set B, and vice versa. 

Thus, the bipartite graph is obtained 𝐾4,4. We demonstrate that every other vertex is an independent 

vertex. Assume, without losing generality, that   is not isolated. So, there is a vertex 

[
(𝑎, 𝑐)
(𝑏, 𝑑)

] ∈ 𝑉(𝐶𝑎𝑦2(𝐺, 𝑆)) such that (𝑥1, 𝑥3) − (𝑎, 𝑐)  ,  (𝑥1, 𝑥3) − (𝑏, 𝑑)  , (𝑥1, 𝑥4) − (𝑎, 𝑏) and 

(𝑥1, 𝑥4) − (𝑏, 𝑑). So,  (𝑎, 𝑐) = (𝑥1, 𝑥4) or (𝑎, 𝑐) = (𝑥2, 𝑥3). If  (𝑎, 𝑐) = (𝑥1, 𝑥4) , then  (𝑎, 𝑐) −

(𝑥1, 𝑥4) then it implies that (𝑥1, 𝑥4) − (𝑥1, 𝑥4)  which is a contradiction. Similarly, If (𝑎, 𝑐) =

(𝑥2, 𝑥3) , then  (𝑎, 𝑐) − (𝑥1, 𝑥4) which implies that (𝑥2, 𝑥3)  − (𝑥1, 𝑥4) and gain it is a contradiction. 

Hence, [
(𝑥1, 𝑥3)
(𝑥1, 𝑥4)

] is an isolated vertex. The following procedure may be used to other vertices as 

well. There are these solitary vertices in an amount of  42 − 8 = 8, and hence  𝐶𝑎𝑦2(𝐺, 𝑆) = 𝐾4,4 ∪

8𝑃1. The graph of 𝐶𝑎𝑦2(𝐺, 𝑆) in this case, is shown below.  

                

The graph 𝑃2 × 𝑃2                          A component of graph 𝐶𝑎𝑦2(𝐺, 𝑆) of 𝑃2 × 𝑃2 

In the next Theorem, we generalized the Cayley graph for each 𝑚=3 when the common Cayley graph 

is 𝑃2 × 𝑃2. 

Lemma 6.  Let 𝐶𝑎𝑦(𝐺, 𝑆) = 𝑃2 × 𝑃2, then 𝐶𝑎𝑦3(𝐺, 𝑆) = 𝐾8,8 ∪ 48𝑃1. 

Proof: Suppose that  𝐺1 = 𝑃2  with vertex set {𝑥1, 𝑥2}  and 𝐺2 = 𝑃2  with vertex set {𝑥3, 𝑥4}  and 

𝐶𝑎𝑦(𝐺, 𝑆) = 𝑃2 × 𝑃2. So, 𝐶𝑎𝑦(𝐺, 𝑆) is a cycle of lenψth 4 and its vertex set is  

𝑉(𝐶𝑎𝑦(𝐺, 𝑆)) = {(𝑥1, 𝑥3), (𝑥1, 𝑥4), (𝑥2, 𝑥3), (𝑥2, 𝑥4)}  

and the set of four edψes {(𝑥1, 𝑥3)(𝑥1, 𝑥4), (𝑥1, 𝑥3)(𝑥2, 𝑥3), (𝑥2, 𝑥3)(𝑥2, 𝑥4), (𝑥2, 𝑥4)(𝑥1, 𝑥4)} 

Since the Cayley graph is a cycle (𝑥1, 𝑥3) −  (𝑥1, 𝑥4) − (𝑥2, 𝑥4) −  (𝑥2, 𝑥3) − (𝑥1, 𝑥3). Then, we have 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 5s (2024) 

 

200 
https://internationalpubls.com 

43 = 64 vertices in  𝐶𝑎𝑦3(𝐺, 𝑆) and 𝑉(𝐶𝑎𝑦3(𝐺, 𝑆)) = {[
𝑎
𝑏
𝑐

] |𝑎, 𝑏, 𝑐 ∈ 𝑉(𝐶𝑎𝑦(𝐺, 𝑆))}. So,  

𝑉(𝐶𝑎𝑦3(𝐺, 𝑆)) = {[

(𝑥𝑖 , 𝑥𝑗)

(𝑥𝑘, 𝑥𝑙)

(𝑥𝑟 , 𝑥𝑠)

]      ∶    𝑖, 𝑗, 𝑘, 𝑙, 𝑟, 𝑠 = 1,2,3,4 }. Therefore, we have two independent sets 

 

It is clear that every vertex in set A is adjacent to all vertices in set B and vice versa. Thus, we ψet 

the bipartite graph 𝐾8,8. We demonstrate that every other vertex is an independent vertex. Absent 

loss of generality, suppose that [

(𝑥𝑖, 𝑥𝑗)

(𝑥𝑘, 𝑥𝑙)
(𝑥𝑟 , 𝑥𝑠)

] is not isolated where 𝑖, 𝑘, 𝑟 = 1,2 and 𝑗, 𝑙, 𝑠 = 3,4. So, there 

is a vertex [

(𝑎, 𝑏)

(𝑐, 𝑑)
(𝑒, 𝑓)

] ∈ 𝑉(𝐶𝑎𝑦3(𝐺, 𝑆)) such that (𝑥𝑖, 𝑥𝑗) − (𝑎, 𝑏)  ,  (𝑥𝑖, 𝑥𝑗) − (𝑐, 𝑑)  , (𝑥𝑖 , 𝑥𝑗) − (𝑒, 𝑓) 

and  (𝑥𝑘, 𝑥𝑙) − (𝑎, 𝑏)  ,  (𝑥𝑘 , 𝑥𝑙) − (𝑐, 𝑑)  , (𝑥𝑘, 𝑥𝑙) − (𝑒, 𝑓) and (𝑥𝑟 , 𝑥𝑠) − (𝑎, 𝑏)  ,  (𝑥𝑟 , 𝑥𝑠) − (𝑐, 𝑑)  

, (𝑥𝑟 , 𝑥𝑠) − (𝑒, 𝑓) . but (𝑥𝑖, 𝑥𝑗) is of deψree 2. So,  (𝑎, 𝑏) = (𝑥𝑖, 𝑥𝑗) or (𝑎, 𝑏) = (𝑥𝑘, 𝑥𝑙) or (𝑎, 𝑏) =

(𝑥𝑟 , 𝑥𝑠). If  (𝑎, 𝑏) = (𝑥𝑖, 𝑥𝑗) , then it implies that (𝑥𝑖, 𝑥𝑗) − (𝑥𝑖, 𝑥𝑗)  which is a contradiction. 

Likewise, If (𝑎, 𝑏) = (𝑥𝑘, 𝑥𝑙) and (𝑎, 𝑏) = (𝑥𝑟 , 𝑥𝑠)  we ψet the a contradiction. Hence, the rest 

vertices [

(𝑥𝑖 , 𝑥𝑗)

(𝑥𝑘, 𝑥𝑙)
(𝑥𝑟 , 𝑥𝑠)

] are isolated vertices. We can prove by the same method as above for more 

vertices. There are these solitary vertices in an amount of |𝑉(𝐶𝑎𝑦3(𝐺, 𝑆)| − (|𝐴| + |𝐵|) = 43 −

(8 + 8) = 48, and hence  𝐶𝑎𝑦3(𝐺, 𝑆) = 𝐾8,8 ∪ 48𝑃1. The graph of 𝐶𝑎𝑦3(𝐺, 𝑆) is shown below.  

               

 



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 5s (2024) 

 

201 
https://internationalpubls.com 

 

A component of graph 𝐶𝑎𝑦3(𝐺, 𝑆) of 𝑃2 × 𝑃2 

In the next Theorem, we generalized the Cayley graph for each 𝑚 ≥ 2 when the common Cayley graph 

is 𝑃2 × 𝑃2. 

Theorem 7.  Let 𝐶𝑎𝑦(𝐺, 𝑆) = 𝑃2 × 𝑃2, then the generalized Cayley graph 𝐶𝑎𝑦𝑚(𝐺, 𝑆) is the graph  

𝐾2𝑚,2𝑚 ∪ (2𝑚+1(2𝑚−1 − 1))𝑃1 for all 𝑚 ≥ 2. 

Proof: Suppose that 𝐺1 = 𝑃2  with vertex set {𝑥1, 𝑥2}  and 𝐺2 = 𝑃2  with vertex set {𝑥3, 𝑥4}  and 

𝐶𝑎𝑦(𝐺, 𝑆) = 𝑃2 × 𝑃2. So, 𝐶𝑎𝑦(𝐺, 𝑆) is a cycle of lenψth 4 and its vertex set is  

𝑉(𝐶𝑎𝑦(𝐺, 𝑆)) = {(𝑥1, 𝑥3), (𝑥1, 𝑥4), (𝑥2, 𝑥3), (𝑥2, 𝑥4)}  

and the set of edψes is (𝑥1, 𝑥3) − (𝑥1, 𝑥4) − (𝑥2, 𝑥4) − (𝑥2, 𝑥3) − (𝑥1, 𝑥3) . So, 𝑉 =

𝑉(𝐶𝑎𝑦𝑚(𝐺, 𝑆)) = {[𝑎1, 𝑎2, … , 𝑎𝑚]𝑡   |𝑎1, 𝑎2, ⋯ , 𝑎𝑚 ∈ 𝑉(𝐶𝑎𝑦(𝐺, 𝑆))} . Therefore, 

|𝑉(𝐶𝑎𝑦𝑚(𝐺, 𝑆))| = 4𝑚. Consider the subsets 𝐴 and 𝐵 of 𝑉 as follows: 

𝐴 = {  [𝑎1, 𝑎2, … , 𝑎𝑚]𝑡 ∶  𝑎𝑖 ∈ {𝑥1, 𝑥3}, 𝑖 = 1,2, … , 𝑚}  and 𝐵 = { [𝑎1, 𝑎2, … , 𝑎𝑚]𝑡  ∶  𝑎𝑖 ∈

{𝑥2, 𝑥4}, 𝑖 = 1,2, … , 𝑚}. We can see that A and B are independent sets and that every vertex from 

one is adjacent to another set using the same technique used in the demonstration of the preceding 

lemma. As a result, the entire bipartite network is induced by the union of disjoint sets A∪ ̇B, and the 

remaining vertices are all isolated vertices. Consequently, 𝐶𝑎𝑦𝑚(𝐺, 𝑆) = 𝐾2𝑚,2𝑚 ∪

 (2𝑚+1(2𝑚−1 − 1))𝑃1 

for all   𝑚 ≥  2.   

In the next lemma, we find the generalized Cayley graph for the special case 𝑛 = 2 when 

𝐶𝑎𝑦(𝐺, 𝑆) = 𝑃2 × 𝐶3. 

Theorem 8. Let 𝐶𝑎𝑦(𝐺, 𝑆) = 𝑃2 × 𝐶3, then 𝐶𝑎𝑦2(𝐺, 𝑆) has ((𝑃2 × 𝐶3) ∘ 2𝑃1) ∪ 18𝑃1 as a subgraph. 

Proof: Suppose that  𝐺1 = 𝑃2 with vertex set {𝑥1, 𝑥2} and 𝐺2 = 𝐶3 with vertex set {𝑥3, 𝑥4, 𝑥5} and 

𝐶𝑎𝑦(𝐺, 𝑆) = 𝑃2 × 𝐶3. So, 𝑉(𝐶𝑎𝑦(𝐺, 𝑆)) = {(𝑥1, 𝑥3), (𝑥1, 𝑥4), (𝑥1, 𝑥5), (𝑥2, 𝑥3)(𝑥2, 𝑥4), (𝑥2, 𝑥5)}   

and |𝑉(𝐶𝑎𝑦(𝐺, 𝑆)| = 6 and 𝐸(𝐶𝑎𝑦(𝐺, 𝑆)) = {(𝑥1, 𝑥3)(𝑥1, 𝑥4), (𝑥1, 𝑥3)(𝑥2, 𝑥3), (𝑥2, 𝑥3)(𝑥2, 𝑥4), 

(𝑥2, 𝑥4)(𝑥1, 𝑥4), (𝑥2, 𝑥4)(𝑥2, 𝑥5), (𝑥2, 𝑥3)(𝑥2, 𝑥5), (𝑥1, 𝑥3)(𝑥1, 𝑥5), , (𝑥1, 𝑥4)(𝑥1, 𝑥5), (𝑥2, 𝑥5)(𝑥1, 𝑥5)T

he graph 𝐶𝑎𝑦(𝐺, 𝑆) = 𝑃2 × 𝐶3 shown in below.  



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 5s (2024) 

 

202 
https://internationalpubls.com 

 

Then, we have 62 = 36 vertices in  𝐶𝑎𝑦2(𝐺, 𝑆) and 𝑉(𝐶𝑎𝑦2(𝐺, 𝑆)) = {[
𝑎
𝑏

] |𝑎, 𝑏 ∈ 𝑉(𝐶𝑎𝑦(𝐺, 𝑆))} =  

 

 

Therefore, each vertex [
(𝑥𝑖, 𝑥𝑗)

(𝑥𝑖, 𝑥𝑗)
]  has deψree 4 and it is adjacent to the vertices [

(𝑥𝑖 , 𝑥𝑗+1)

(𝑥𝑖+1, 𝑥𝑗)
] 

and  [
(𝑥𝑖+1, 𝑥𝑗)

(𝑥𝑖, 𝑥𝑗+1)
]  and  [

(𝑥𝑖, 𝑥𝑗+1)

(𝑥𝑖, 𝑥𝑗+1)
]  and  [

(𝑥𝑖 , 𝑥𝑗+2)

(𝑥𝑖 , 𝑥𝑗+2)
] . The other vertices are isolated. The graph 

𝐶𝑎𝑦2(𝐺, 𝑆) is shown in below.  



Communications on Applied Nonlinear Analysis 

ISSN: 1074-133X 

Vol 31 No. 5s (2024) 

 

203 
https://internationalpubls.com 

 

References 

[1] Farrokhi DΨ, M., Rajabian, M., & Erfanian, A. (2019). Relative Cayley graphs of finite ψroups. Asian-European 

Journal of Mathematics, 12(07), 2050003. 

[2] Frucht, R., Harary, F. On the Corona of two graphs. Aeq. Math. 4, 322–325 (1970). 

[3] S. Mohammadi, Some ψeneralizations of Cayley graph and Intersection graph, Ph.D Thesis, Ferdowsi University of 

Mashhad, Mashhad, Iran, 2020. 

[4] Neamah, A. A., Erfanian, A., & Majeed, A. H. (2022). On A Generalized Cayley Graph of Column Matrices Of 

Elements Of A Finite Ψroup. Mathematica (1222-9016), 64(2). 

[5] Neamah, A. A., Majeed, A. H., & Erfanian, A. (2022). The generalized Cayley graph of complete graph K_nand 

complete multipartite graphs K_(n,n) and K_(n,n,n). Iraqi Journal of Science, 3103-3110. 

[6] Neamah, A. A., Erfanian, A., & Majeed, A. H. (2023, December). The structure of generalized Cayley graph when 

Cay (G,S)= K_(n,n,n,n). In AIP Conference Proceedinψs (Vol. 2834, No. 1). AIP Publishinψ. 

[7] Neamah, S. A., & Erfanian, A. (2023). Some Results on the Generalized Cayley Graph of Complete Graphs. Iraqi 

Journal of Science, 3424-3436. 

[8] Kelarev, A. V. (2002). On undirected Cayley graphs. Australasian Journal of Combinatorics, 25, 73-78. 

[9] Rajabian, M., & Erfanian, A. (2018). Relative Cayley graphs of finite ψroups. Asian-European Journal of 

Mathematics, 12.