J.
Indones.
Math.
Soc.
Vol.
No.
, pp.
130Ae136.
CAYLEY GRAPHS VERSUS ALGEBRAIC GRAPHS
Pranjali1 .
Amit Kumar2 , and Tanuja Yadav3 Department of Mathematics.
University of Rajasthan.
JLN Marg.
Jaipur 302004.
India, pranjali48@gmail.
Department of Mathematics and Statistics.
Banasthali Vidyapith.
Banasthali-304022.
India, amitsu48@gmail.
com, yadav.
tanuja17@gmail.
Abstract.
Let e be a finite group and let S OI e be a subset.
The Cayley graph, denoted by Cay.
S) has vertex set e and two distinct vertices x, y OO e are joined by a directed edge from x to y if and only if there exists s OO S such that x = sy.
In this manuscript, we characterize the generating sets S for which Cay.
S) is isomorphic to some algebraic graphs, namely, unit graphs, co-unit graphs, total graph and co-total graphs.
Key words and Phrases: Cayley Graphs.
Finite group.
Generating sets.
Preamble The research in algebraic combinatorics is aims at exposing the relationship between algebra and graph theory and at advancing applications of one to the other.
In the last decade, many authors have studied algebraic graphs(Viz.
, zero-divisor graph, total graph, unit graph, co-total graph, maximal graph, co-unit graphs, prime graph, et.
associated to algebraic structures.
Perhaps the best known one is the Cayley graph .
of a group.
Let e be an abelian group.
For Zn , the group of integer modulo n, the sets Z(Zn ) and U (Zn ) are defined as.
U (Zn ) = .
: gcd.
, .
= .
and Z(Zn ) = .
, .
6= .
For generating set S of e we define the Cayley graph of e to be the .
graph Cay.
S) with vertices e, the set of elements of e, and two distinct vertices x and y are adjacent if and only if there exists s OO S such that x = sy.
Thus Cay.
S) is connected graph when S OI U .
, and Cay.
S) is disconnected 2020 Mathematics Subject Classification: 13A15, 05C22, 05C75, 16P10.
Received: 22-01-2019, accepted: 05-04-2021.
Cayley Graphs Versus Algebraic Graphs when S OI Z.
With this motivation in Section 2, we characterize the generating set S for which Cay.
S) is isomorphic to one of the graph, namely, unit graphs, co-unit graphs, total graph and co-total graphs.
However, for convenience of the reader, we shall also gather some definitions and results for Cayley graphs which will be used in the sequel.
In Section 3, we give several basic results about Cayley graphs associated with some specific generating sets.
We have also established the results that gives the relation between Cayley graph and unit graphs, co-unit graphs, total graph and co-total graphs.
Further, in view of Theorem 3.
3 we have shown that the study on the notion of unit graph, co-unit graphs, co-total graphs and total graph for the group Zn is a particular case for the study on the Cay(Zn .
S) associated with specify generating sets, viz.
U (Zn ) and Z 0 (Zn ).
Throughout, many examples are given to illustrate the theory, and we pose several questions.
For detail study about co-total graph, and co-unit graphs, we refers to reader .
In what follows, all consider graphs are simple, i.
, undirected graphs in which any two vertices are joined by at most one edge and without loops.
Throughout.
Zn will denote the group of integers modulo n.
and Cn .
Kn , and will denote an n-cycle, and the complete graph on n vertices, respectively.
To avoid trivialities, we implicitly assume when necessary that graphs are nonempty.
For terminology and notation from group theory or graph theory not defined in this paper, we refer the reader to .
, respectively.
Generating Sets In general, given any group e, a generating set S of e is merely a nonempty set such that e OO / S and if a OO S, then aOe1 OO S, where AoeAo is the identity element of e.
Consequently.
S 6= I and if all the elements of e are self inverse, then all possible generating sets are 2n Oe 2.
In view of this definition, the following result recognize the structure of such generating set.
In 2011.
Beny and Rakhmonov .
have derived a formula for number of Cayley graphs on Zn .
Theorem 2.
Let e O = Zn and S be a generating set of e and N (S) be the collection of all generating sets.
Then nOe1 .
If n is odd, then |N (S)| = 2 2 Oe 1.
If n is even, then |N (S)| = 2 2 Oe 1.
Example 2.
Consider the group Z4 , then there are precisely three generating sets .
, .
, .
, 2, .
If we take n = 4 in Theorem 2.
1, then we get |N (S)| = 3.
In the similar vein, consider the group Z5 , then there are precisely three generating sets .
, .
, .
, .
, 2, 3, .
If we take n = 5 in Theorem 2.
1, then we get |N (S)| = 3.
Theorem 2.
Let e O = Zt y Z2n .
Then the number of generating sets consisting of only nonzero self-inverse elements are 2.
Oe.
Oe 1.
Proof.
Let us consider e O = Zt2 y Z2n and our aim is to show that number of generating sets consisting of only self-inverse elements are 2.
Oe.
Oe 1.
Note that Pranjali1 .
Amit Kumar2 and Tanuja Yadav3 each element of Zt2 is self inverse and there are precisely two self inverse elements namely Ao0Ao and AonAo in Z2n .
By fixing exactly one from Ao0Ao and AonAo at .
th position all self inverse elements can be obtained.
Firstly, by fixing zero at .
th position in .
tuple, i.
1 , a2 , .
, at , .
, there are 2t Oe 1 choices for ai and hence 2t Oe 1 nonzero self inverse elements.
In the similar way, by fixing AonAo at .
th position in .
tuple, i.
, .
1 , a2 , .
, at , .
there are 2t choices for ai and hence for self inverse elements.
Therefore the total number of non-zero self inverse elements in e are 2t 1 -1.
Now it is easy to see that the number of generating sets consisting of only self-inverse elements are 2.
Oe.
Oe 1.
Remark 2.
Let e O = Z2 y Z2n .
Then there are exactly three nonzero self-inverse elements and hence six generating set consisting of nonzero self-inverse elements.
Cayley Graphs and Algebraic Graphs Let (A.
O) be an algebraic structure.
A graph G := (V.
E) is called an algebraic graph, if V OI A and the adjacency rule is due to binary operation AoOAo of algebraic In this section, we establish the results that gives the relation between Cayley graph and algebraic graphs, namely, unit graph, co-unit graph, total graphs and co-total graphs.
Theorem 3.
Let GE(Zn ) and TE .
(Zn )) be co-unit graph, and co-total graph.
Then for a positive integer AonAo the following holds:
Cay(Zn .
S) O = GE(Zn ), when S = U (Zn ).
Cay(Zn .
S) O = TE .
(Zn )), when S = Z 0 (Zn ).
Proof.
It is clear that the vertex set of both Cay(Zn .
S) and GE(Zn ) are same.
Let vi , vj OO V (Cay(Zn .
S)).
Then vi is adjacent to vj if and only if vi Oe vj OO S.
First, when S = U (Zn ), this implies that vi Oe vj OO U (Zn ).
This shows that .
i , vj ) OO E(Cay(Zn .
S)) if and only if .
i , vj ) OO E(GE(Zn )).
Therefore.
Cay(Zn .
S) O = GE(Zn ).
On the other hand, when S = Z 0 (Zn ).
This implies that vi Oe vj OO Z 0 (Zn ).
This shows that .
i , vj ) OO E(Cay(Zn .
S)) if and only if .
i , vj ) OO E(TE .
(Zn ))).
Therefore.
Cay(Zn .
S) O = TE .
(Zn )).
Lemma 3.
Let n be an even positive integer.
Then for all a, b OO Zn the following .
For S = U (Zn ).
a Oe b OO S if and only if a b OO S.
For S = Z 0 (Zn ).
a Oe b OO S if and only if a b OO S O .
Proof.
For the case .
(N.
Let n be an even positive integer and S = U (Zn ).
Then U (Zn ) consists of all odd positive integer less than n.
If a Oe b OO S = U (Zn ), then a Oe b must be an odd number.
Note that a b = a Oe b 2b, which is an odd number, and hence a b OO S.
(N.
If a b OO S = U (Zn ), then a b must be an odd number.
Note that in this Cayley Graphs Versus Algebraic Graphs case exactly one a or b must be odd and hence a Oe b is an odd number.
Therefore a Oe b OO S.
For the case .
(N.
if S = Z 0 (Zn ).
Then Z 0 (Zn ) consists of all even positive integer less than n.
If a Oe b OO S = Z 0 (Zn ), then a Oe b must be an even Note that a b = a Oe b 2b, which is an even number may be zero, and hence a b OO S O .
(N.
If a b OO S = Z 0 (Zn ) O .
, then a b must be an even number.
Note that in this case either both a and b are even or both are odd.
Then a Oe b is an even number, and hence a Oe b OO S.
Theorem 3.
Let G(Zn ) and T .
(G(Zn ))) be unit graph and total graph, respectively.
Then for an even positive integer AonAo the following holds:
O G(Zn ), when S = U (Zn ).
Cay(Zn .
S) = O T .
(Zn )), when S = Z 0 (Zn ).
Cay(Zn .
S) = Proof.
To show the result it is suffices to show the isomorphism between the given Let AonAo be an even positive integer.
To tackle the case .
, define a function f : V (Cay(Zn .
S)) Ie V (G(Zn )) such that if v is odd.
= n Oe v, otherwise.
Clearly f is a bijective function.
Now we want to show that under this f adjacency is preserved.
To do this, let vi and vj be two vertices of Cay(Zn .
S).
Then vi is adjacent to vj , if vi Oe vj OO S = U (Zn ) which is odd and this is possible only when either both vi , vj OO Z 0 (Zn ) or exactly one of them vi or vj belong to U (Zn ).
For the first possibility, one of vi or vj must be odd although belong to Z 0 (Zn ), then f .
i ) = vi and f .
j ) = n Oe vj , this implies that f .
i ) f .
j ) = vi n Oe vj = n .
i Oe vj ) OO U (Zn ).
Next, if vi OO U (Zn ) and vj OO Z 0 (Zn ), then f .
i ) = vi and f .
j ) = nOevj and the sum f .
i ) f .
j ) = vi nOevj = n .
i Oevj ) OO U (Zn ).
This implies that f .
i ) f .
j ) OO U (Zn ).
This shows that .
i , vj ) OO E(Cay(Zn .
S)) Ni .
i ), f .
j )) OO E(G(Zn )).
Therefore Cay(Zn .
S) O = G(Zn ), when S = U (Zn ).
For the case .
, again define a function f : V (Cay(Zn .
S)) Ie V (T .
(Zn ))) such that if v is even f .
= n Oe v, otherwise.
Clearly f is a bijective function.
Now we want to show that under this f adjacency is preserved.
To do this, let vi and vj be two vertices of Cay(Zn .
S).
Then vi is adjacent to vj , if vi Oe vj OO S = Z 0 (Zn ).
Then there are two possibilities, either vi Oe vj is even or odd.
First, if vi Oevj is even, then either both vi , vj are even or odd.
Let us suppose both vi and vj are even.
Then the sum f .
i ) f .
j ) = vi vj which is even and belong to Z(Zn ) .
sing Lemma 3.
Now, if both vi , vj are odd, then the sum f .
i ) f .
j ) = .
Oe vi ) .
Oe vj ) = 2n Oe .
i vj ) again belong to Z(Zn ).
Hence in the first possibility, vi Oe vj OO Z 0 (Zn ) if and only if f .
i ) f .
j ) OO Z(Zn ).
Next, in the second possibility, if vi Oe vj OO Z 0 (Zn ) and it is odd, then note that at least one Pranjali1 .
Amit Kumar2 and Tanuja Yadav3 of vi or vj must be odd.
Let us suppose vi be odd.
Then the sum f .
i ) f .
j ) = .
Oe vi ) vj = n Oe .
i Oe vj ).
Consequently, f .
i ) f .
j ) OO Z(Zn ).
Hence in both the possibilities adjacency is preserved under f .
Therefore Cay(Zn .
S) O = T .
(Zn )), when S = Z 0 (Zn ).
Remark 3.
It may hence be observed from Theorem 3.
3 that the study on the notion of unit graph and total graph for Zn is a particular case for the study on the Cay(Zn .
S) associated with specify generating sets, viz.
U (Zn ) and Z 0 (Zn ).
Theorem 3.
If S1 OI S2 , then Cay(Zn .
S1 ) is a subgraph of Cay(Zn .
S2 ).
Proof.
Let S1 OI S2 .
Clearly, the vertex set of Cay(Zn .
S1 ) and Cay(Zn .
S2 ) is same and is equal to .
, 1, 2, .
, n Oe .
Let vi and vj be two arbitrary vertices in Cay(Zn .
S1 ).
If vi and vj are adjacent in Cay(Zn .
S1 ), then vi Oe vj OO S1 .
This implies that vi Oe vj OO S2 as S1 OI S2 .
Therefore each edge of Cay(Zn .
S1 ) is also an edge of Cay(Zn .
S2 ).
Hence.
Cay(Zn .
S1 ) is a subgraph of Cay(Zn .
S2 ).
Theorem 3.
Let e O = Zt2 yZ2n and S be the collection of all self inverse elements of e.
If S 0 OI S and |S 0 | = 1, then Cay.
S 0 ) O = K2 O K2 O A A A O K2 .
Oetimes .
If S 0 = S, then Cay.
S) O = K|S .
O K|S .
O A A A O K|S .
nOetimes Proof.
Case .
: Let S 0 OI S and |S 0 | = 1.
Then Cay.
S 0 ) is 1-regular graph.
The only possible 1-regular graph is either K2 or copies of K2 .
Since there are 2t 1 .
vertices in Cay.
S 0 ), this indicates that Cay.
S 0 ) is isomorphic to copies of K2 .
Also to form K2 only two vertices are required.
Hence, there are 2t A n copies of K2 .
Therefore Cay.
S 0 ) O = K2 O K2 O A A A O K2 .
Oetimes Case .
: From the Theorem 2.
3 clearly, .
t 1 Oe .
non-zero self inverse elements in e.
This implies that |S| = 2.
Oe 1.
Then.
Cay.
S) is 2.
Oe 1 regular graph.
Let V 0 = {.
1 , a2 , .
, at , at 1 ) : ai OO .
, .
O i O .
and at 1 OO .
, .
The set V 0 is subset of V (Cay.
S)) and specifically it is the collection of all self inverse elements, i.
V 0 = S O .
, 0, .
, 0, .
Let vi and vj be two arbitrary vertices of V 0 .
Then vi Oe vj = .
1 , c2 , .
, ct , ct 1 ) \ .
, 0, , .
, .
: ci OO .
, .
O i O .
and ct 1 OO .
, .
This implies that vi Oe vj OO S, also vi and vj are arbitrary which indicates that for all vi , vj OO V 0 , vi Oe vj OO S.
Therefore all the vertices of V 0 are mutually adjacent and each of them have degree 2.
Oe 1.
Also no vertex of V 0 is adjacent to other vertices of Cay.
S) as Cay.
S) is 2.
Oe 1 regular.
Let V 00 = {.
1 , a2 , .
, at , at 1 .
: ai OO .
, .
O i O .
and at 1 OO .
, .
Let vi0 and vj0 be two arbitrary vertices of V 00 .
Then vi0 Oe vj0 = .
1 , d2 , .
, dt , dt 1 ) \ .
, 0, , .
, 0, .
: di OO .
, .
O i O .
and dt 1 OO .
, .
This implies that vi0 Oe vj0 OO S, also vi0 and vj0 are arbitrary which indicates that for all vi0 , vj0 OO V 00 , vi0 Oe vj0 OO S.
Therefore all the vertices of V 00 are again Cayley Graphs Versus Algebraic Graphs mutually adjacent and each of them have degree 2.
Oe 1.
Also no vertex of V 00 is adjacent to other vertices of Cay.
S) as Cay.
S) is 2.
Oe 1 regular.
Following the same procedure, one get the copies of K2t 1 .
Since there are n.
vertices in Cay.
S), so there will be precisely n copies of K2t 1 are obtained.
Therefore.
Cay.
S) O = K|S .
O K|S .
O A A A O K|S .
nOetimes Corollary 3.
Let e O = Zt2 and S be the collection of all self inverse elements of e.
Then the followings holds:
If S 0 OI S and |S 0 | = 1, then Cay.
S 0 ) O = K2 O K2 O A A A O K2 .
If S = S, then Cay.
S ) O = K2t .
tOe1 )Oetimes Proof.
By taking n = 1 in Theorem 3.
6, the proof follows.
Theorem 3.
Let e O = Zt2 yZ2n and S be the collection of all self inverse elements of e.
Then for n = 1.
Cay.
S) is connected.
Proof.
Invoking Theorem 3.
6 and Corollary 3.
Cay.
S 0 ) O = K2t 1 , and hence Theorem 3.
Let S = {.
, 1, .
, 1, at ), at OO U (Z2n )}.
Then Cay(Zt2 y Z2n .
S) O G(Zt2 y Z2n ) O = GE(Zt2 y Z2n ).
Proof.
Let us consider Z2n and we want to show that Cay(Zt2 y Z2n .
S) O = G(Zt2 y Z2n ) O = G(Zt2 y Z2n ) = GE(Z2 y Z2n ).
For this first we will show Cay(Z2 y Z2n .
S) O and then Cay(Zt2 y Z2n .
S) O = GE(Zt2 y Z2n ).
To do this let us suppose on contrary Cay(Zt2 y Z2n .
S) G(Zt2 y Z2n ) Although V (Cay(Zt2 y Z2n .
S)) = V (G(Zt2 y Z2n )).
Let vi = .
1 , a2 , .
, at , at 1 ) and vj = .
1 , b2 , .
, bt , bt 1 ) be two vertices of Cay(Zt2 y Z2n .
S).
Then vi and vj are adjacent in Cay(Zt2 y Z2n .
S) whenever vi Oe vj OO S, i.
, .
1 Oe b1 , a2 Oe b2 , .
, at Oe bt , at 1 Oe bt 1 ), ai Oe bi = 1 for all 1 O i O t and at 1 Oe bt 1 OO U (Z2n ).
Since ai , bi OO Z2 , ai Oe bi = 1 gives us that one of ai or bi must be Ao0Ao.
This implies that ai bi = 1 for all 1 O i O t.
As at 1 Oe bt 1 OO U (Z2n ), this implies that at 1 bt 1 OO U (Z2n ).
Hence .
i , vj ) OO E(Cay(Zt2 y Z2n .
S)).
This implies that .
i , vj ) OO E(G(Zt2 yZ2n )).
This shows that each edge of Cay(Zt2 yZ2n .
S) is also an edge of G(Zt2 y Z2n ).
Therefore only possibility is to be .
is that two vertices vi0 vj0 are adjacent in G(Zt2 y Z2n ) but not in Cay(Zt2 y Z2n .
S), i.
, vi0 vj0 OO U (Z2n ), but vi0 Oe vj0 OO / S.
From Lemma 3.
2, vi0 vj0 OO U (Z2n ) implies that vi0 Oe vj0 OO U (Z2n ).
This gives us S OC U (Zt2 y Z2n ), a contradiction.
Hence our assumption is wrong.
Therefore Cay(Zt2 y Z2n .
S) O = G(Zt2 y Z2n ).
Now to show that Cay(Zt2 y Z2n .
S) O = GE(Zt2 y Z2n ).
Let vi = .
1 , a2 , .
at , at 1 ) and vj = .
1 , b2 , .
, bt , bt 1 ) be two vertices of Cay(Zt2 yZ2n .
S), although V (Cay(Zt2 y Z2n .
S)) = V (GE(Zt2 y Z2n )).
Then vi and vj are adjacent in Cay(Zt2 y Pranjali1 .
Amit Kumar2 and Tanuja Yadav3 Z2n .
S) whenever vi Oe vj OO S.
Since S = {.
, 1, .
, 1, ak ), ak OO U (Z2n )}, which indicates that .
i , vj ) OO E(Cay(Zt2 yZ2n .
S)) if and only if .
i , vj ) OO E(GE(Zt2 yZ2n )).
This shows that each edge of Cay(Zt2 y Z2n .
S) is also an edge of GE(Zt2 y Z2n ).
Therefore Cay(Zt2 y Z2n .
S) O = GE(Zt2 y Z2n ).
Theorem 3.
Let S = {.
1 , a2 , .
, atOe1 , at )}, with either at least one ai = 0 for 1 O i O t Oe 1 and at OO Z2n \ .
or ai = 1 for all i, 1 O i O t Oe 1 and at OO Z(Z2n ) O .
Then Cay(Zt2 y Z2n .
S) O = T .
(Zt2 y Z2n )) O = TE .
(Zt2 y Z2n )).
Proof.
The proof can be obtained by the arguments that are analogous to those given in the proof of Theorem 3.
Acknowledgement.
This paper is dedicated to Prof.
Bajpai (Great academician, excellent poet and very polite personality of Rani Durgavati University.
Jabalpur.
Indi.
on the occasion of his coming 65th birthday.
REFERENCES