# Cayley Graphs over LA-Groups and LA-Polygroups

Authors: Nabilah Abughazalah; Naveed Yaqoob; Asif Bashir
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

The purpose of this paper is the study of simple graphs that are generalized Cayley graphs over LA-polygroupsGCLAP−graphs. In this regard, we construct two new extensions for building LA-polygroups. Then, we define Cayley graph over LA-group and GCLAP-graph. Further, we investigate a few properties of them to show that each simple graph of order three, four, and five (except cycle graph of order five which may or may not be a GCLAP-graph) is a GCLAP-graph and then we prove this result.


---

## Body

## 1. Introduction

The origins of graph theory can be traced back to Euler’s work [1] on the königsberg bridges problem 1735, which thusly prompted the idea of an Eulerian graph. Graph is a mathematical portrayal of a grid and it portrays the relationship between lines and points.The idea of Cayley graph was introduced by Cayley [2] in 1878. Cayley graph has been widely studied in both directed and undirected forms. To study the characteristics of Cayley graphs, refer the papers [3–6].First time Marty [7] introduced the concept of algebraic hyperstructures, which is a suitable extension of classical algebraic structures. Since then, a lot of works have been written on this topic. For a brief analysis of this theory, see [8,9]. In the books [10–13], we can see the applications of hyperstructures in lattices, cryptography, graph, automata, probability, geometry, and hypergraphs. A very good presentation of polygroup theory is in [14], which is utilized to consider color algebra [15–17] and hypergraph theory in [18] by Berge.The theory of left almost structures was first defined by Kazim and Naseeruddin [19] in 1972. Subsequently, Mushtaq and Kamran [20] established a new concept of left almost group (nonassociative group) called LA-group. The theory of left almost hyperstructures was first introduced by Hila and Dine [21] in the form of left almost semihypergroups, which was further investigated by Yaqoob et al. [22] and Amjad et al. [23]. In [24], Yaqoob et al. introduced the concept of LA-polygroups.Recently, Heidari et al. [25] introduced a suitable generalization of Cayley graphs that is defined over polygroups GCP−graphs and showed that each simple graph of order ≥5 is a GCP-graph.In this paper, we construct two new extensions for building LA-polygroups. Then, we define the idea of Cayley graph over LA-group and GCLAP-graph. In particular, we proved some properties of them in order to show that each simple graph of order three, four, and five (except cycle graph of order five which may or may not be a GCLAP-graph) is a GCLAP-graph.


## 2. Preliminaries and Notations

This section contains some basic definitions of graph theory (see [26]) and left almost theory (see [24]).A graph is represented byΦ=R,D, where R is the set of vertices and D is the set of edges. Note that R is the order of a graph and D in a graph is its size. The graph Kn is known as complete graph if every couple of vertices form an edge, where n is the number of vertices. In specific, K1 is known as trivial graph and Nn is known as null graph having no edges and n vertices.IfΦ=R,D is a graph such that R=R′∪R″andR′∩R″=∅, where R′ and R″ are subsets of R and edges of the form d,f|d∈R′andf∈R″, then Φ=Km,n is known as complete bipartite graph, where R′=m and R″=n. In specific, K1,n is known as star graph. The complement of a simple graph Φ=R,D is denoted by Φ¯, where Φ¯=R,D¯ such that D¯=d,f|d,f∉D. Let Φ=R,D and Φ′=R′,D′ be two graphs. Then, Φ′ is known as subgraph of Φ, if R′⊆R and D′⊆D. A subgraph Φ′⊆Φ is known as induced subgraph, if Φ′ contains each and every edge d,f∈D with d,f∈R′. Two graphs Φ=R,D and Φ′=R′,D′ are said to be isomorphic, if ∃, a bijection, γ:R⟶R′ such that z,a∈D⇔γz,γa∈D′. We denote this by Φ≅Φ′. Let Φ=R,D and Φ′=R′,D′ be two graphs. Then, Φ∪Φ′=R″,D″, where R″=R∪R′ and D″=D∪D′ and joint of two graphsΦ∨Φ′=R″,D″ with R″=R∪R′ and D″=D∪D′∪d,f|d∈R,f∈R′. A graph Φ=R,D having no self edges and no multiple edges is known as simple graph.Definition 1 (see [27]).
IfΦ=R,D is a graph and we form a sequence of vertices (ordered from left to right) d1,d2,d3,…,dn such that there is just one edge between every two succesive vertices and there are no other edges known as path. A path on n vertices is denoted by Pn.Definition 2 (see [27]).
A graph is said to be a connected graph if there exists at least one path between every two vertices.Definition 3 (see [27]).
If all vertices have degree two of a connected graph, then it is called a cycle. A cycle graph hasn vertices, represented by Cn.Definition 4 (see [20]).
A groupoidG is called a left almost group, i.e., LA-group, if(i)
∃e∈G such that ed=d for all d∈G,(ii)
∀d∈G,∃d∗∈G such that dd∗=e,(iii)
wfd=dfw, ∀d,f,w∈G.Example 1 (see [20]).
LetGn=t1,t2,…,tn where n≥3, under binary operation ∗ which is defined as(1)ti∗tj=tk,k≡j+1−imodn.
Then,Gn,∗ is an LA-group. For n=5, we have the Cayley (Table 1).Table 1
LA-group.
∗t1t2t3t4t5t1t1t2t3t4t5t2t5t1t2t3t4t3t4t5t1t2t3t4t3t4t5t1t2t5t2t3t4t5t1Definition 5 (see [24]).
A multivalued systemL,∘,e,−1, where e∈L−1, is a unitary operation and ∘ maps L×L into the family of nonempty subsets of L which is called LA-polygroup, if the following postulates hold for all d,f,w∈L:(i)
Left invertive law:d∘f∘w=w∘f∘d,(ii)
Reproducibility axiom:d∘L=L∘d=L,(iii)
∃ is a left identity L∋e such that f=e∘f,(iv)
f−1∘f∩f∘f−1∑e,(v)
d∈f∘w⟹f∈d∘w−1.Example 2 (see [24]).
Consider a finite setQn=t1,t2,t3,…,tn, where n≥3. Then, Qn is an LA-polygroup under the following hyperoperation:(2)ti∗tj=tj,fori=1,tk,forj=1andk≡2−imodQn,Qn,forj≠1,i≠1,i=j,Qn∖t1,forj≠1,i≠1,i≠j.
Forn=5, we have the Cayley (Table 2).Table 2
LA-polygroup.
∗t1t2t3t4t5t1t1t2t3t4t5t2t5QnQn\t1Qn\t1Qn\t1t3t4Qn\t1QnQn\t1Qn\t1t4t3Qn\t1Qn\t1QnQn\t1t5t2Qn\t1Qn\t1Qn\t1QnExample 3 (see [24]).
ConsiderL1=1,2,3,4 with the hyperoperation ∘, given in Table 3.
Then,L1=1,2,3,4,∘,1,−1 is an LA-polygroup.
Notations. All LA-polygroups are represented by L,M,N,… and the underlying sets are represented by L,M,N,… Also, L∗=L\e and A−1=a−1:a∈A. Now, we establish two new extensions for making LA-polygroups.Table 3
LA-polygroup.
∘123411234242,3,42,41,2,3332,41,32,4421,3,42,42,3,4


### 2.1.I Extension of an LA-Polygroup by a Set: LT

Suppose thatL,∘,e,−1 is an LA-polygroup and L∩T=∅, where T is a nonempty set. Put M=L∪T, e⊎d=d, for every d∈M and ∀d,f∈M∗=d∈M:d≠e; we define(3)d−I=d−1,ifd∈L,d,ifd∈T,d⊎e=d∘e,ifd∈L,d,ifd∈T,d⊎f=d∘f∪T,ifd,f∈L,L∪T,ifd=f∈T,M∗,otherwise.The systemM,⊎,e,−I is known as the extension of LA-polygroup L by a set T and represented by LT.Theorem 1.
LetL,∘,e,−1 be an LA-polygroup and T be a nonempty set such that L∩T=∅. Then, LT is an LA-polygroup.Proof.
Suppose thatLT=M, L∪T=M, L∩T=∅, and d,f,w∈M. If d,f,w⊆L∗, then(4)d⊎f⊎w=d∘f∘w∪T∪M∗=w∘f∘d∪T∪M∗=w⊎f⊎d.
If exactly one ofd,f,w∈L is equal to the left identity, then(5)d⊎f⊎w=d∘f∘w∪T=w∘f∘d∪T=w⊎f⊎d.
If exactly two ofd,f,w∈L are equal to the left identity, then(6)d⊎f⊎w=d∘f∘w=w∘f∘d=w⊎f⊎d.
Ifd,f,w⊈L, then d⊎f⊎w=M=w⊎f⊎d. Thus, left invertive law holds. Now, we prove axiom (v) of Definition 5. Let d,f,w∈M such that w∈d⊎f, thenCase 1. If d,f,w∈L, then we have done.Case 2.a If w∈L∗, then we have the following possibilities:(i)
Ifd∈T and f∈L∗, then T⊆w⊎f−I⇒d∈w⊎f−I;(ii)
Iff∈T and d∈L∗, then d∈w⊎f−I=w⊎f=M∗⇒d∈w⊎f−I;(iii)
Ifd,f∈T, then d∈w⊎f−I=w⊎f=M∗⇒d∈w⊎f−I.Case 2.b If w=e, then w∈d⊎f⇒d=f−I and w⊎f−I=e⊎d=d⇒d∈w⊎f−I.Case 3.a If w∉L and d,f∈M∗, then(7)w⊎f−I=M∗,ifw≠f,w⊎f−I=M,ifw=f.Hence,d∈w⊎f−I.Case 3.b If w∉L andd=e, then w∈d⊎f⇒w=f∈T and w⊎f−I=f⊎f−I=f⊎f=M, hence d∈w⊎f−I.Case 3.c If w∉L andf=e, then
w∈d⊎f=d⇒w=d and w⊎f−I=w=d, hence d∈w⊎f−I.
Thus, condition (v) of Definition 5 holds and hence the theorem is proved.Example 4.
LetL2=1,2,3,4,∘,1,−1 be an LA-polygroup with the Cayley (Table 4).
Then,M2=L25,6 is an LA-polygroup with six elements and the Cayley (Table 5), where M2=1,2,3,4,5,6.Table 4
LA-polygroup.
∘123411234232,31,24321,32,3444441,2,3Table 5
LA-polygroup.
⊎1234561123456232,3,5,61,2,5,64,5,6M2∗M2∗321,3,5,62,3,5,64,5,6M2∗M2∗444,5,64,5,61,2,3,5,6M2∗M2∗55M2∗M2∗M2∗M2M2∗66M2∗M2∗M2∗M2∗M2Note thatM2∗=M2∖1=2,3,4,5,6.


### 2.2.II Extension of an LA-Polygroup by a Set: LT⋄

Suppose thatL,∘,e,−1 is an LA-polygroup and L∩T=∅, where T is a nonempty set such that T=∪i=1nti (ordered from left to right, i.e., t1,t2,t3,…,tn). Put L∪T=M and e⊎d=d,∀d∈M. We define(8)d−I=d−1,ifd∈L,d,ifd∈T,d⊎e=d∘e,ifd∈L,d,ifd∈T,d⊎f=d∘f,ifd,f∈L,ti,ifd∈L,f=ti∈TORd=ti∈T,f∈Lwhere1≤i≤n,ti,ifd=ti,f=tj∈Twherei>j,tj,ifd=ti,f=tj∈Twherei<j,L,ifd=t1=f∈T,L∪Ai,ifd=ti+1=f∈Twhere1≤i≤n−1,where Ai=∪h=1ith. The system M,⊎,e,−I is known as the extension of LA-polygroup L by a set T and represented by LT⋄.Theorem 2.
LetL,∘,e,−1 be an LA-polygroup and T be a nonempty set such that L∩T=∅. Then, LT⋄ is an LA-polygroup.Proof.
Suppose thatLT⋄, L∪T=M, L∩T=∅, and d,f,w∈M.
Ifd,f,w⊆L, then clearly left invertive law holds.
Ifd,f,w⊈L, then we consider the following cases:Case 1. If w∉L and d,f∈L, then w⊎f⊎d=w=d⊎f⊎w.Case 2. If w=sk, f=sj∉L, and d∈L, then(9)d⊎f⊎w=w⊎w=w⊎f⊎d,ifk=j,d⊎f⊎w=w=w⊎f⊎d,ifk>j,d⊎f⊎w=f=w⊎f⊎d,ifk<j,Case 3. If w=sk, f=sj, d=si∉L in the following way:(i)
such thatk>j>i, then(10)d⊎f⊎w=si⊎sj⊎sk=sk=sk⊎sj⊎si=w⊎f⊎d,(ii)
such thati=j, then(11)d⊎f⊎w=si⊎sj⊎sk=si⊎si=sk⊎sj⊎si=w⊎f⊎d,ifk<i=j≠1,d⊎f⊎w=si⊎sj⊎sk=sk=sk⊎sj⊎si=w⊎f⊎d,ifk>i=j,(iii)
such thatj=k, then(12)d⊎f⊎w=si⊎sj⊎sk=sj⊎sj=sk⊎sj⊎si=w⊎f⊎d,ifi<j=k≠1,d⊎f⊎w=si⊎sj⊎sk=si=sk⊎sj⊎si=w⊎f⊎d,ifi>j=k.
Thus, left invertive law holds. Now, we prove axiom (v) of Definition 5. Let d,f,w∈M such that w∈d⊎f. Then, we consider the following cases:Case 1. If w∈T, then either w=d∈T or w=f∈T or s1≠d=f∈T:(i)
Ifw=d∈T, then d∈w⊎f−I=d⊎f−I=d,(ii)
Ifw=f∈T and d∈L, then L⊆f⊎f=w⊎f−I⇒d∈w⊎f−I; if w=f∈T and d∈T, then w=f=sjj≠1 and L∪Aj−1⊆w⊎f−I⇒d∈w⊎f−I,(iii)
Ifs1≠d=f∈T, then w⊎f−I=w⊎f=f=d⇒d∈w⊎f−I.Case 2. If w∈L, then d=f∈T and w⊎f−I=w⊎f=f=d⇒d∈w⊎f−I.
Thus, condition (v) of Definition 5 holds and hence the theorem is proved.Example 5.
LetL3=1,2,3,∘,1,−1 be an LA-polygroup with the Cayley (Table 6).
Then,M3=L34,5⋄ is an LA-polygroup with five elements and the Cayley (Table 7), where M3=1,2,3,4,5.
This is an LA-polygroup and not a polygroup.Table 6
LA-polygroup.
∘1231123232,31,2,3321,2,32,3Table 7
LA-polygroup.
⊎12345112345232,31,2,345321,2,32,34544441,2,35555551,2,3,4


## 2.1.I Extension of an LA-Polygroup by a Set: LT

Suppose thatL,∘,e,−1 is an LA-polygroup and L∩T=∅, where T is a nonempty set. Put M=L∪T, e⊎d=d, for every d∈M and ∀d,f∈M∗=d∈M:d≠e; we define(3)d−I=d−1,ifd∈L,d,ifd∈T,d⊎e=d∘e,ifd∈L,d,ifd∈T,d⊎f=d∘f∪T,ifd,f∈L,L∪T,ifd=f∈T,M∗,otherwise.The systemM,⊎,e,−I is known as the extension of LA-polygroup L by a set T and represented by LT.Theorem 1.
LetL,∘,e,−1 be an LA-polygroup and T be a nonempty set such that L∩T=∅. Then, LT is an LA-polygroup.Proof.
Suppose thatLT=M, L∪T=M, L∩T=∅, and d,f,w∈M. If d,f,w⊆L∗, then(4)d⊎f⊎w=d∘f∘w∪T∪M∗=w∘f∘d∪T∪M∗=w⊎f⊎d.
If exactly one ofd,f,w∈L is equal to the left identity, then(5)d⊎f⊎w=d∘f∘w∪T=w∘f∘d∪T=w⊎f⊎d.
If exactly two ofd,f,w∈L are equal to the left identity, then(6)d⊎f⊎w=d∘f∘w=w∘f∘d=w⊎f⊎d.
Ifd,f,w⊈L, then d⊎f⊎w=M=w⊎f⊎d. Thus, left invertive law holds. Now, we prove axiom (v) of Definition 5. Let d,f,w∈M such that w∈d⊎f, thenCase 1. If d,f,w∈L, then we have done.Case 2.a If w∈L∗, then we have the following possibilities:(i)
Ifd∈T and f∈L∗, then T⊆w⊎f−I⇒d∈w⊎f−I;(ii)
Iff∈T and d∈L∗, then d∈w⊎f−I=w⊎f=M∗⇒d∈w⊎f−I;(iii)
Ifd,f∈T, then d∈w⊎f−I=w⊎f=M∗⇒d∈w⊎f−I.Case 2.b If w=e, then w∈d⊎f⇒d=f−I and w⊎f−I=e⊎d=d⇒d∈w⊎f−I.Case 3.a If w∉L and d,f∈M∗, then(7)w⊎f−I=M∗,ifw≠f,w⊎f−I=M,ifw=f.Hence,d∈w⊎f−I.Case 3.b If w∉L andd=e, then w∈d⊎f⇒w=f∈T and w⊎f−I=f⊎f−I=f⊎f=M, hence d∈w⊎f−I.Case 3.c If w∉L andf=e, then
w∈d⊎f=d⇒w=d and w⊎f−I=w=d, hence d∈w⊎f−I.
Thus, condition (v) of Definition 5 holds and hence the theorem is proved.Example 4.
LetL2=1,2,3,4,∘,1,−1 be an LA-polygroup with the Cayley (Table 4).
Then,M2=L25,6 is an LA-polygroup with six elements and the Cayley (Table 5), where M2=1,2,3,4,5,6.Table 4
LA-polygroup.
∘123411234232,31,24321,32,3444441,2,3Table 5
LA-polygroup.
⊎1234561123456232,3,5,61,2,5,64,5,6M2∗M2∗321,3,5,62,3,5,64,5,6M2∗M2∗444,5,64,5,61,2,3,5,6M2∗M2∗55M2∗M2∗M2∗M2M2∗66M2∗M2∗M2∗M2∗M2Note thatM2∗=M2∖1=2,3,4,5,6.


## 2.2.II Extension of an LA-Polygroup by a Set: LT⋄

Suppose thatL,∘,e,−1 is an LA-polygroup and L∩T=∅, where T is a nonempty set such that T=∪i=1nti (ordered from left to right, i.e., t1,t2,t3,…,tn). Put L∪T=M and e⊎d=d,∀d∈M. We define(8)d−I=d−1,ifd∈L,d,ifd∈T,d⊎e=d∘e,ifd∈L,d,ifd∈T,d⊎f=d∘f,ifd,f∈L,ti,ifd∈L,f=ti∈TORd=ti∈T,f∈Lwhere1≤i≤n,ti,ifd=ti,f=tj∈Twherei>j,tj,ifd=ti,f=tj∈Twherei<j,L,ifd=t1=f∈T,L∪Ai,ifd=ti+1=f∈Twhere1≤i≤n−1,where Ai=∪h=1ith. The system M,⊎,e,−I is known as the extension of LA-polygroup L by a set T and represented by LT⋄.Theorem 2.
LetL,∘,e,−1 be an LA-polygroup and T be a nonempty set such that L∩T=∅. Then, LT⋄ is an LA-polygroup.Proof.
Suppose thatLT⋄, L∪T=M, L∩T=∅, and d,f,w∈M.
Ifd,f,w⊆L, then clearly left invertive law holds.
Ifd,f,w⊈L, then we consider the following cases:Case 1. If w∉L and d,f∈L, then w⊎f⊎d=w=d⊎f⊎w.Case 2. If w=sk, f=sj∉L, and d∈L, then(9)d⊎f⊎w=w⊎w=w⊎f⊎d,ifk=j,d⊎f⊎w=w=w⊎f⊎d,ifk>j,d⊎f⊎w=f=w⊎f⊎d,ifk<j,Case 3. If w=sk, f=sj, d=si∉L in the following way:(i)
such thatk>j>i, then(10)d⊎f⊎w=si⊎sj⊎sk=sk=sk⊎sj⊎si=w⊎f⊎d,(ii)
such thati=j, then(11)d⊎f⊎w=si⊎sj⊎sk=si⊎si=sk⊎sj⊎si=w⊎f⊎d,ifk<i=j≠1,d⊎f⊎w=si⊎sj⊎sk=sk=sk⊎sj⊎si=w⊎f⊎d,ifk>i=j,(iii)
such thatj=k, then(12)d⊎f⊎w=si⊎sj⊎sk=sj⊎sj=sk⊎sj⊎si=w⊎f⊎d,ifi<j=k≠1,d⊎f⊎w=si⊎sj⊎sk=si=sk⊎sj⊎si=w⊎f⊎d,ifi>j=k.
Thus, left invertive law holds. Now, we prove axiom (v) of Definition 5. Let d,f,w∈M such that w∈d⊎f. Then, we consider the following cases:Case 1. If w∈T, then either w=d∈T or w=f∈T or s1≠d=f∈T:(i)
Ifw=d∈T, then d∈w⊎f−I=d⊎f−I=d,(ii)
Ifw=f∈T and d∈L, then L⊆f⊎f=w⊎f−I⇒d∈w⊎f−I; if w=f∈T and d∈T, then w=f=sjj≠1 and L∪Aj−1⊆w⊎f−I⇒d∈w⊎f−I,(iii)
Ifs1≠d=f∈T, then w⊎f−I=w⊎f=f=d⇒d∈w⊎f−I.Case 2. If w∈L, then d=f∈T and w⊎f−I=w⊎f=f=d⇒d∈w⊎f−I.
Thus, condition (v) of Definition 5 holds and hence the theorem is proved.Example 5.
LetL3=1,2,3,∘,1,−1 be an LA-polygroup with the Cayley (Table 6).
Then,M3=L34,5⋄ is an LA-polygroup with five elements and the Cayley (Table 7), where M3=1,2,3,4,5.
This is an LA-polygroup and not a polygroup.Table 6
LA-polygroup.
∘1231123232,31,2,3321,2,32,3Table 7
LA-polygroup.
⊎12345112345232,31,2,345321,2,32,34544441,2,35555551,2,3,4


## 3. Cayley Graphs over LA-Groups and LA-Polygroups

Definition 6.
Suppose thatG is an LA-group and C is a subset of G such that(i)
1∉C,(ii)
C−1=C; then, Cayley graph CayLAG,C of G relative to C is the simple graph which has vertex set G and edge set(13)D=g,gs|g≠gs,whereg∈Gands∈C.Example 6.
The Cayley graphs of the LA-groupG5=t1,t2,t3,t4,t5,∗ given in Example 1, with connection sets t2 and t2,t3, are shown in Figures 1 and 2. For C=t2, we have(14)t1,t1∗t2=t1,t2t2,t2∗t2=t2,t1t3,t3∗t2=t3,t5t4,t4∗t2=t4,t4t5,t5∗t2=t5,t3.
ForC=t2,t3, we have(15)t1,t1∗t2=t1,t2t3,t3∗t2=t3,t5t1,t1∗t3=t1,t3t4,t4∗t3=t4,t5.Figure 1
CayLAG5,t2.Figure 2
CayLAG5,t2,t3.Definition 7.
Given an LA-polygroupL=L,∘,e,−I and L⊆C≠∅ such that C=C−I, say the connection set. Then, we define the generalized Cayley graph over LA-polygroup GCLAPL;C which is the simple graph having vertex set L and the edge set(16)D=d,f|d≠fandd∘e∘f∩C≠∅.
If we have an LA-polygroupL and a connection set C such that GCLAPL;C≅Λ, then the graph Λ is known as a GCLAP-graph.
Here, we give few examples of GCLAP-graphs.Example 7.
The generalized Cayley graph of the left almost polygroupL4=1,2,3,4,∘,1,−1, with connection set C=3,4 which is shown in Figure 3, where”°” is defined in Table 8.Figure 3
GCLAPL4;3,4.Table 8
LA-polygroup.
∘123411234231,2,32,3,42322,3,41,2,3344321Example 8.
The generalized Cayley graph of the left almost polygroupL5=1,2,3,4,5,∘,1,−1 with connection set 2,3 which is shown in Figure 4, where”∘” is defined in Table 9.Figure 4
GCLAPL5;4,5.Table 9
LA-polygroup.
∘12345112345232,31,245321,32,34544441,2,3,4,54,555554,51,2,3,4,5


## 4. Which Simple Graphs Are GCLAP-Graphs?

First, we point out a few types of simple graphs that are GCLAP-graphs. After that, we infer that each simple graph of order three, four, and five (except cycle graph of order five which may or may not be a GCLAP-graph) is a GCLAP-graph.Lemma 1.
Every Cayley graph is a GCLAP-graph.Proof.
Since every LA-group is an LA-polygroup, therefore, by Definition7, the result holds.Lemma 2.
Every complete graph of order at least three is a GCLAP-graph.Proof.
LetQn,∗,t1−1 be an LA-polygroup, where n≥3 (as defined in Example 2). Then, GCLAPQn;Qn∖t1 are isomorphic to the complete graphs on n vertices, where n≥3. Hence, it is proved.Lemma 3.
Show that each star graph of order at least three is a GCLAP-graph.Proof.
Suppose thatL=Gntn+1⋄, where n≥3 and Gn is defined in Example 1. Then, Cayley table for L is given in Table 10.
Now, by considering connection setC=tn+1, we can see that Sn≅GCLAPL;C.Table 10
LA-polygroup.
⊎t1t2...tntn+1t1tn+1t2tn+1.Gn.....tntn+1tn+1tn+1tn+1...tn+1t1,t2,t3,…,tnLemma 4.
IfΦ is a GCLAP-graph. Then, show that Φ∪nK1 is also a GCLAP-graph, where n≥1.Proof.
LetΦ be a GCLAP-graph. Then, we have a left almost polygroup L and a connection set C such that Φ≅GCLAPL;C. Suppose that Φn=Φ∪nK1 and Zm=∪t=1mzt. By Extension (II) and Definition 7, we have Φ1≅GCLAPLZ1⋄;C. Now, by using induction, Φm≅GCLAPQ;C, where Q=LZm⋄ and C is a connection set. Hence, Φm+1≅GCLAPQzm+1⋄;C. Thus, Φn is a GCLAP−graph for every n∈ℕ.Definition 8.
Letm∈1,2,3,… and q∈2,3,4,…,m−1. Then, the m,q-pseudo complete graph is known as the complement of the graphSq∪Nm−q and represented by U^m,q. A graph Φ is known as a pseudocomplete graph if Φ≅U^m,q for some m∈1,2,3,… and q∈2,3,4,…,m−1.Example 9.
Pseudocomplete graphs on five vertices are shown in Figure5.Figure 5
Pseudocomplete graphs on five vertices.Lemma 5.
Ifm∈1,2,3,… and b,q∈2,3,…,m−1, then the following statements hold:(i)
U^m,q is connected,(ii)
Ifq≠b then U^m,q≠U^m,b,(iii)
A connected graphΦ of order m is a pseudocomplete graph ⇔; it contains Km−1 as a subgraph.Lemma 6.
All pseudocomplete graphs are GCLAP-graphs.Proof.
LetΦ=U^m,q be a pseudocomplete graph, where m≥1 and q∈2,3,4,…,m−1. Consider the LA-polygroup L=Q34,5,6,…,m, where Q3=1,2,3,∗,1,−1, given in Example 2, and the connection set C=q+1,q+2,…,m. Then, GCLAPL;C¯ is isomorphic to the graphSq∪Nm−q. Hence, U^m,q≅GCLAPL;C.Definition 9.
The expansion of the graphΦ, represented by Φ+, is the join of the graph Φ and K1, i.e., Φ+=Φ∨K1.Lemma 7.
Show that the expansion of a GCLAP-graph is a GCLAP-graph.Proof.
LetΛ≅GCLAPL;C, where L is a left almost polygroup having n elements and C is a connection set. Suppose that Q=Ln+1⋄ and C′=C∪n+1. Then, Φ+≅GCLAPQ;C′.Definition 10.
LetΦ=G,D be a graph, g∈G, and f∉G. The faulty join graph, represented by ∇g, is the graph such that ∇gΦ,f=G′,D′, where G′=G∪f and D′=D∪f,h:g≠h∈G. Moreover, a graph is known as ∇1-graph if it is isomorphic to ∇1Φ,f, where Φ=GCLAPL;C such that L is a left almost polygroup having n elements, f∉L ,and C is a connection set.Lemma 8.
Every∇1-graph is a GCLAP-graph.Proof.
Suppose thatΛ is a ∇1-graph having n vertices. So, we have a left almost polygroup L having n elements and a connection setC such that Λ≅∇1GCLAPL;C,n+1. Let Ln+1=Q, then we have(17)∇1GCLAPL;C,n+1≅GCLAPQ;C.Hence,Λ is a GCLAP-graph.Up to here, we have determined a few types of GCLAP-graphs. Now, we confine ourselves to the graphs of order at most five (except cycle graph of order five) and show that every simple graph of order three, four, and five (except cycle graph of order five which may or may not be a GCLAP-graph) is a GCLAP-graph. In Appendix, we have shown all simple connected graphs of order three, four, and five (except cycle graph of order five) and denote them byΩ1,Ω2,…,Ω28.Theorem 3.
All simple graphs of order three, four, and five (except cycle graph of order five which may or may not be a GCLAP-graph) are GCLAP-graphs.Proof.
Suppose thatΦ is a simple graph of order three, four, and five (except cycle graph of order five). Then, as per the connectivity of Φ, two cases can be thought of:Case 1. If Φ is a connected graph, then we have six subcases:Subcase (i) (cycles and complete graphs):Consider the LA-polygroupL4 as in Example 7. Then, GCLAPL4;3,4≅Ω5, so Ω5 is a GCLAP-graph. Also, since Ω2, Ω8, and Ω28 are complete graphs, therefore, by Lemma 2, they are GCLAP-graphs.Subcase (ii) (star graphs): Think about LA-polygroupL3 as given in Example 5, then GCLAPL3;2≅Ω1. Also, since Ω4 and Ω9 are star graphs, so by Lemma 3, they are GCLAP-graphs.Subcase (iii) (path graphs): Consider the LA-polygroupL4 and LA-group G5 as defined in Examples 7 and 6, respectively. Then, Ω3≅GCLAPL4;2, so Ω3 is a GCLAP-graph. Also, since CayLAG5,t2,t3≅Ω11, therefore, by Lemma 1, Ω11 is a GCLAP−graph.Subcase (iv) (pseudocompleted graphs): Definition8 implies that Ω6,Ω7,Ω22,Ω25, and Ω27 are pseudocomplete graphs and by Lemma 6, they are GCLAP−graphs.Subcase (v) (expansion graphs): Think about the LA-polygroupL4 as in Example 7 and L6=1,2,3,4,∘,1,−1, given in Table 11.(18)Ω12≅GCLAPL4;4+,Ω16≅Ω1∪K1+,Ω17≅GCLAPL6;4+,Ω21≅Ω4+,Ω23≅Ω3+,Ω26≅Ω5+.Definition9 and above cases suggest that the graphs Ω12,Ω16,Ω17,Ω21,Ω23, and Ω26 are expansion graphs of GCLAP-graphs and by Lemma 7, we infer that they are GCLAP-graphs.Subcase (vi) (∇10 graphs):Consider three LA-polygroupsL4, L2, andL1 as in Example 7, Example 4, and Example 3, respectively, then the following isomorphisms hold:(19)Ω10≅∇1GCLAPL4;4,5,Ω13≅∇1GCLAPL2;2,5,Ω14≅∇1GCLAPL1;3,5,Ω18≅∇1GCLAPL4;2,5,Ω24≅∇1GCLAPL4;2,4,5.Thus, the graphsΩ10,Ω13,Ω14,Ω18, and Ω24 are ∇1-graphs. By Lemma 8, we conclude that they are GCLAP-graphs. In the end, if we consider the left almost group G5 given in Example 6 and LA-polygroup, L7=1,2,3,4,5,∘,1,−1 with the Cayley (Table 12).Then, by Lemma1, we conclude that Ω19≅CayLAG5;a2,a3,a5 and hence the following isomorphisms hold:(20)Ω15≅GCLAPL7;3,5,Ω20≅GCLAPL7;3,4.Thus, all simple connected graphs of order three, four, and five (except cycle graph of order five which may or may not be a GCLAP-graph) are GCLAP-graphs.Case 2. If Φ is not connected. We have two subcases:Subcase (i): ifΦ contains two nontrivial parts, then Φ is isomorphic to K2∪K2, K2∪Ω1, and K2∪Ω2. We have K2∪K2≅GCLAPL1;3, K2∪Ω1≅GCLAPL7;3, and K2∪Ω2≅GCLAPL7;2,5, where L1 and L7 are given in Example 3 and Subcase (vi), respectively.Subcase (ii): ifK1 is a subgraph of Φ, then Φ≅nK1∪Λ, for n≥1 and Λ is isomorphic to K2∪K2 or isomorphic to CayLAG3,t2 or a connected graph of order <5. By Lemma 4, we conclude that Φ is a GCLAP−graph which completes the proof.The question that usually comes to mind is what happens ifΦ>5; we present this query as an open problem [28, 29].Table 11
LA-polygroup.
∘123411234232,3,41,2,42,3321,3,42,3,42,3442,32,31,4Table 12
LA-polygroup.
∘123451123452213453441,25343351,24555431,2



---

*Source: 4226232-2021-05-10.xml*