Page 1 of 6

LABELINGS IN THE CONTEXT OF

DIGRAPHS

S. BALA1

, S.SUNDARRAJ2

, K.THIRUSANGU3

1,2,3 Department of Mathematics, S.I.V.E.T. College,

Gowrivakkam, Chennai-600073, Tamilnadu, India

E-mail.: 1

yesbala75@gmail.com,

2

sjsundar89@gmail.com,

3

kthirusangu@gmail.com

Abstract

In 1878, Cayley constructed a graph for a given group with a generating set which is now popularly known as

Cayley graphs. A directed graph or digraph G(V,E) consists of a finite set of points called vertices and set of

directed arrows between the vertices. Let G be a finite group and S be a generating subset of G. The Cayley

digraph denoted by Cay(G,S), is the digraph whose vertices are the elements of G, and there is an arc from g to gs

whenever g∈G and s∈S. If S=S-1

then there is an arc from g to gs if and only if there is an arc from gs to g. The

Cayley graphs and Cayley digraphs are excellent models for interconnection networks. For example hypercube,

butterfly, and cube-connected cycle’s networks are Cayley graphs. In this paper we investigate the existence of

Mean cordial labeling, 3-Total cordial labeling, Even sum cordial labeling and Mean labeling in Cayley digraphs

associated with algebraic group namely 2-generated 2-groups by presenting algorithms.

Keywords: Cayley digraph, Graph Labeling

Introduction

Graph theory:

The first paper in graph theory was written by LEONHARD EULER (father of graph theory) in 1736 about the

solution of unsolved problem of his day known as KONIGSBERG bridge problem.

Graph Labeling:

The concept of graph labeling was introduced by Rosa in 1967. A graph labeling is an assignment of integers to the

vertices (or) edges (or) both to certain conditions.

If the domain of the mapping is the set of vertices (or edges), then the labeling is called a vertex labeling (or an edge

labeling).

Cordial Labeling:

The concept of cordial labeling was introduced by Cahit. A function f : V→ {0, 1} is said to be a cordial labeling if

each edge uv has the label | f(u) − f(v) | such that the number of vertices labeled 0 and the number of vertices labeled 1

differ by at most one and the number of edges labeled 0 and the number of edges labeled 1 differ by at most one. A graph

which admits cordial labeling is called cordial graph.

Mean cordial labeling:

The concept of mean cordial labeling was introduced by Ponraj et al. Let f be a function from V(G) to {0, 1, 2}.

For each edge uv of G, assign the label

f u +f(v)

2

. f is called a mean cordial labeling of G if vf

i −vf

j ≤1 and

ef

i − ef

j ≤1, i, j∈{0, 1, 2} where vf(x) and ef(x) denote the number of vertices and edges labeled with x (x=0,1,2)

respectively. A graph with a mean cordial labeling is called mean cordial graph.

3-total sum cordial labeling:

The concept of 3-total sum cordial labeling was introduced by Tenguria and Verma. Let G be a graph and let f be

a map f:V(G){0, 1, 2}. For each edge uv assign the label [f(u)+f(v)] mod 3. Then the map f is called 3-total sum cordial

labeling of G. If |f(i)-f(j)|≤1, i, j∈{0, 1, 2} where f(x) denotes the total number of vertices and edges labeled with x={0, 1,

2}.

Even sum cordial labeling:

The concept of even sum cordial labeling was introduced by S. Abhirami et al. Let G= (V,E) be a simple graph

and f:V{1,2,3...|V|} be a bijection. For each edge uv, assign the label 1 if f(u)+f(v) is even and the label 0 otherwise. f is

called an even sum cordial labeling if |ef(0)- ef(1)|≤1, where ef(0) and ef(1) denote the number of edges labeled with 0 and

number of edges labeled with 1 respectively.

Mean labeling:

The concept of mean labeling was introduced by Somasundaram et al. Let G be {p, q} graph. A graph G is mean graph

if f is 1-1 function f:V{0, 1, 2, ..., q} such that when each edge e= uv is labeled with

f

*

(e)=

f u +f(v)

2

if f(u)+ f(v) is even

f

*

(e)=

f u +f v +1

2

if f(u)+ f(v) is odd

the resultant edges are distinct.

The International journal of analytical and experimental modal analysis

Volume XII, Issue VII, July/2020

ISSN NO:0886-9367

Page No:1267

Page 2 of 6

Cayley digraph for the 2-generated 2-groups:

The Cayley digraph for the 2-generated 2-group Cay(G,(α,β)) has n vertices and 2n arcs. Let us denote the vertex set of

Cay(G,(α,β)) as V={v1, v2, v3,...,vn). Define the arc set of Cay(G,(α,β)) as E(Eα,Eβ) where Eα={(v,αv)|vεV} and

Eβ={(v,βv)|vεV}. Denote the arcs in Eα as {gα(vi)|viεV} and Eβ as {gβ(vi)|viεV}. Clearly each vertex in Cay(G,(α,β)) has

exactly two out going arcs out of which one arc is from the set Eα and another is from the set Eβ.

A group G is said to be a p-group if o(G)=pm

, m≥1. It is said to be 2-generated if the minimal generating set of G has

exactly two elements. It is said to be a 2-group if p=2. We consider the groups of order 2m

=n.

Main Result

1. Mean Cordial Labeling

In this section we prove the existence of mean cordial labeling for Cayley digraph of 2-generated 2-groups by presenting

algorithm.

Algorithm 1.1:

Input: Cayley digraph for the 2-generated 2-groups

Procedure Mean cordial labeling for Cayley digraph of 2-generated 2-groups

V {v1, v2, v3, ..., vn}

E (Eα ,Eβ ){ e1, e2, e3, ..., e2n}

Eα Set of all outgoing edges generated by α through each vertex of Cay(G,(α,β))

Eβ Set of all outgoing edges generated by β through each vertex of Cay(G,(α,β))

for i=1 to n/4 do

gα(vi)

2 , i ≡ 1 mod 2

1 , i ≡ 0 mod 2

gβ(vi)

1 , i ≡ 1 mod 2

2 , i ≡ 0 mod 2

end for

for i=n

4

+1 to n/2 do

gα(vi)0

gβ(vi)

0 , i ≡ 1 mod 2

1 , i ≡ 0 mod 2

end for

for i=n

2

+1 to n

2

+2 do

gα(vi)

1 , i ≡ 1 mod 2

0 , i ≡ 0 mod 2

gβ(vi)

2 , i ≡ 1 mod 2

1 , i ≡ 0 mod 2

end for

for i=n

2

+3 to n do

gα(vi)2

gβ(vi)

0 , i ≡ 1 mod 2

2 , i ≡ 0 mod 2

end for

end procedure

Theorem 1.1: The Cayley digraph associated with 2-generated 2-groups admits mean cordial labeling.

Proof:

We know that, Cayley digraph for the 2-generated 2-groups has n vertices and 2n edges. Denote the edges set E= {e1,

e2, e3,...,e2n} and vertices set V={v1,v2,...,vn}. The edges are labeled by defining a function ∅

∗

:E{0,1,2} as given

algorithm 1.1.

Clearly the number of edge labeled with 0, 1 and 2 as follows:

Thus the number of edges labeled with 0, the number of edges labeled with 1 and the number of edges labeled with 2

differ at most one.

In order to obtain the labels for the vertices, define the induced map ∅:V{0,1,2} such that for any vi∈V,

∅ (vi)=

∅

∗

gα

vi

+∅

∗

gβ

vi

2

Edge labels For all ‘n’

0 n-3

1 n-3

2 n-2

The International journal of analytical and experimental modal analysis

Volume XII, Issue VII, July/2020

ISSN NO:0886-9367

Page No:1268

Page 3 of 6

For 1≤i≤n

∅(vi)=

0 i ≡ 0 mod 3

1 i ≡ 1 mod 3

2 i ≡ 2 mod 3

Clearly the number of vertices labeled 0, 1 and 2 are follows.

Thus the number of vertices labeled with ‘0’, the number of vertices labeled

with ‘1’ and the number of vertices labeled with ‘2’ differ by at most one.

Hence, the Cayley digraph associated with 2-generated 2-groups admits mean cordial labeling.

Illustration:1.1 Mean cordial labeling for Cayley digraph of 2-generated 2-groups is given in figure 1.

Fig 1: Mean cordial labeling

2. 3-total sum Cordial Labeling

In this section we prove the existence of 3-total sum cordial labeling for Cayley digraph of 2-generated 2-groups by

presenting algorithm.

Algorithm 2.1:

Input: Cayley digraph for the 2-generated 2-groups

Procedure 3-total sum cordial labeling for Cayley digraph of 2-generated 2-groups

V {v1, v2, v3, ..., vn}

E (Eα ,Eβ ){ e1, e2, e3, ..., e2n}

Eα Set of all outgoing edges generated by α through each vertex of Cay(G,(α,β))

Eβ Set of all outgoing edges generated by β through each vertex of Cay(G,(α,β))

for i=1 to n/2 do

gα(vi)

2 , i ≡ 1 mod 2

1 , i ≡ 0 mod 2

end for

for i=n

2

+1 to n

2

+2 do

gα(vi)

0 , i ≡ 1 mod 2

1 , i ≡ 0 mod 2

gβ(vi)0

end for

for i=n

2

+3 to n do

gα(vi)2

gβ(vi)

0 , i ≡ 1 mod 2

1 , i ≡ 0 mod 2

end for

for i=1 to n/4 do

gβ(vi)

0 , i ≡ 1 mod 2

1 , i ≡ 0 mod 2

end for

for i=n

4

+1 to n/2 do

gβ(vi)

0 , i ≡ 1 mod 2

2 , i ≡ 0 mod 2

end for

end procedure

Vertex labels For all ‘n’

0 n-5

1 n-5

2 n-6

The International journal of analytical and experimental modal analysis

Volume XII, Issue VII, July/2020

ISSN NO:0886-9367

Page No:1269

Page 4 of 6

Theorem 2.1: The Cayley digraph associated with 2-generated 2-groups admits 3-total sum cordial labeling.

Proof:

We know that, Cayley digraph for the 2-generated 2-groups has n vertices and 2n edges. Denote the edges set E= {e1,

e2, e3,...,e2n} and vertices set V={v1,v2,...,vn}. The edges are labeled by defining a function ∅

∗

:E{0,1,2} as given

algorithm 2.1.

Clearly the number of edge labeled with 0, 1 and 2 as follows:

Thus the number of edges labeled with 0, the number of edges labeled with 1and the number of edges labeled with 2 differ

at most one.

In order to obtain the labels for the vertices, define the induced map ∅:V{0,1,2} such that for any vi∈V, ∅(vi)

=[∅

*

(gα(vi))+ ∅

*

(gβ(vi))] (mod 2).

For 1≤i≤n

∅(vi)=

0 i ≡ 0 mod 3

1 i ≡ 1 mod 3

2 i ≡ 2 mod 3

Clearly the number of vertices labeled 0, 1 and 2 are follows.

Thus the number of vertices labeled with ‘0’, the number of vertices labeled with ‘1’ and the number of vertices labeled

with ‘2’ differ by at most one.

Hence, the Cayley digraph associated with 2-generated 2-groups admits 3-total sum cordial labeling.

Illustration:2.1 3-total sum cordial labeling of the Cayley digraph of 2-generated 2-groups is given in figure 2.

Fig 2: 3- Total sum cordial labeling

3. Even sum cordial Labeling

In this section we prove the existence of even sum cordial labeling forCayley digraph of 2-generated 2-groups by

presenting algorithm.

Algorithm 3.1:

Input:Cayley digraph for the 2-generated 2-groups

Procedure Even sum cordial labeling for Cayley digraph of 2-generated 2-groups

V {v1, v2, v3, ..., vn}

E (Eα ,Eβ ){ e1, e2, e3, ..., e2n}

Eα Set of all outgoing edges generated by α through each vertex of Cay(G,(α,β))

Eβ Set of all outgoing edges generated by β through each vertex of Cay(G,(α,β))

for i=1 to n do

vii

end for

end procedure

Edge labels For all ‘n’

0 n-2

1 n-3

2 n-3

Vertex labels For all ‘n’

0 (n/2)-2

1 (n/2)-1

2 (n/2)-1

The International journal of analytical and experimental modal analysis

Volume XII, Issue VII, July/2020

ISSN NO:0886-9367

Page No:1270

Page 5 of 6

Theorem 3.1: The Cayley digraph associated with 2-generated 2-groups admits even sum cordial labeling.

Proof:

We know that, Cayley digraph for the 2-generated 2-groups has n vertices and 2n edges. Denote the edges set E= {e1,

e2, e3,...,e2n} and vertices set V={v1,v2,...,vn}. The vertices are labeled by defining a function ∅:V{1, 2, ...,n} as given

algorithm 3.1.

In order to obtain the labels for the edges, define the induced map∅

∗

:E{0,1} such that number of edge label 1 for

∅

*

(gα(vi))+ ∅

*

(gβ(vi)) is even, 0 otherwise.

(i) For 1≤i≤n/4

∅

*

(gα(vi))=1

(ii) For i=n

4

+1≤i≤

n

2

+2

∅

*

(gα(vi))=0

(iii) For i=n

2

+3≤i≤ n

∅

*

(gα(vi))=1

(iv) For 1≤i≤n/2

∅

*

(gβ(vi))=1

(v) For i=n

2

+1≤i≤ n

∅

*

(gβ(vi))=0

Clearly the number of edges labeled 0 and 1 are follows.

Edges label For all ‘n’

0 n

1 n

Thus the number of edge labeled with ‘0’ and the number of edge labeled with ‘1’ differ by at most one.

Hence, the Cayley digraph associated with 2-generated 2-groups admits even sum cordial labeling.

Illustration:3.1 Even sum cordial labeling of theCayley digraph of 2-generated 2-groups is given in figure 3.

Fig 3: Even sum cordial labeling

4. Mean Labeling

In this section we prove the existence of mean labeling forCayley digraph of 2-generated 2-groups by presenting

algorithms.

Algorithm 4.1:

Input: Cayley digraph for the 2-generated 2-groups

Procedure Mean labeling for Cayley digraph for the 2-generated 2-groups

V {v1, v2, v3, ..., vn}

E (Eα ,Eβ ){ e1, e2, e3, ..., e2n}

Eα Set of all outgoing edges generated by α through each vertex of Cay(G,(α,β))

Eβ Set of all outgoing edges generated by β through each vertex of Cay(G,(α,β))

for i=1 to n/4 do

gα(vi)2i+

n+1

3

end for

for i=n

4

+1 to n/2 do

gα(vi)(n+1)-2i

end for

for i=n

2

+1 to n

2

+2 do

gα(vi)3n-2i+2

gβ(vi)

n

2

-2(i-5)

end for

for i=n

2

+3 to n do

The International journal of analytical and experimental modal analysis

Volume XII, Issue VII, July/2020

ISSN NO:0886-9367

Page No:1271

Page 6 of 6

gα(vi)2i-

n

2

gβ(vi)n-2(i-7)

end for

for i=1 to n/2 do

gβ(vi)2i+(n-1)

end for

end procedure

Theorem: 4.1TheCayley digraph associated with 2-generated 2-groups admits mean labeling.

Proof:

We know that, Cayley digraph for the 2-generated 2-groups has n vertices and 2n edges. Denote the edges set E= {e1,

e2, e3,...,e2n} and vertices set V={v1,v2,...,vn}. The edges are labeled by defining a function ∅

∗

:E{1, 2, ...,2n} as given

algorithm 4.1.

In order to obtain the labels for the vertices, define the induced map ∅:VN such that ∅ (vi)=

∅

∗

gα

vi

+∅

∗

gβ

vi

2

for all

integers i, j(i≠j), ∅(vi)≠ ∅(vi).

Thus, ∅ (vi)=2i, 1≤i≤n.

Hence the labels of vi are distinct.

Hence, the Cayley digraph associated with 2-generated 2-groups admits mean labeling.

Illustration:4.1 Mean labeling of the Cayley digraph of 2-generated 2-groups is given in figure 4.

Fig 4: Mean labeling

Conclusion:

In this paper, we proved existence of mean cordial labeling, 3-total sum cordial labeling, even sum cordial labeling and

mean labeling for the Cayley digraph of 2-generated 2-groups.

References:

1. Akers.S.B, and Krishnamurthy.B, A group theoretic model for symmetric Interconnection networks, IEEE Trans. Comput.38(1989), 555-566.

2. Annexstein.F, Baumslag.M, Rosenberg.A.L, Group action graphs and Parallel architectures. SIAM J. Comput.19,(1990), 544-569.

3. Gallian.J.A, A dynamic survey of graph labeling, The Electronic Journal of Combinatorics 18 (2018), #DS6.

4. K.R. Sobha, S. Chandra kumar and P. Sree Devi, International Journal of Pure and Applied Mathematics, Mean Labeling Techniques in some special

graphs, Vol 119 No.15, 2018, 737-740.

5. Poulomi Ghosh, Sumonta Ghosh, Anita Pal, Journal of Informatics and Mathematical Sciences, 3-Total Sum Cordial Labeling on some new graphs,

Vol.9, No.3, pp. 665-673,2017.

6. Raja Ponraj, Muthirulan Sivakumar, Murugesan Sundaram, Open Journal of Discrete Mathematics, Mean Cordial Labeling, 2012, 2, 145-148.

7. Rosa.A, On certain valuations of the vertices of a graph, Theory of graphs (Internat.Symposium, Rome, July 1996), Gordon and Breach, N.Y. and

Dunod Paris (1967), 349-355.

8. S. Abhirami, R. Vikramaprasad, R. Dhavaseelan, International Journal of Mechanical Engineering and Technology, Even sum cordial labeling for some

new graphs, Vol 9, Issue 2, Feb 2018, PP. 214-220.

9. Thirusangu.K, Atulya K. Nagar, Rajeswari.R, Labelings in Cayley’s digraphs, European Journal of Combinatorics, 32(2011), 133-139.

10. Thirusangu.K, Bala.E, Magic and antimagic labeling in Cayley digraphs of 2-generated p-groups, International Journal of Mathematics Research Vol 3.

No.3 (2011), 221-229.

The International journal of analytical and experimental modal analysis

Volume XII, Issue VII, July/2020

ISSN NO:0886-9367

Page No:1272