 Open Access
 Total Downloads : 561
 Authors : Charles Robert Kenneth, Albert William, R.C. Thivyarathi
 Paper ID : IJERTV2IS2188
 Volume & Issue : Volume 02, Issue 02 (February 2013)
 Published (First Online): 28022013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Radio Antipodal Number of Circulant Graphs
Charles Robert Kennetp, Albert William2 and R.C. Thivyarathi3
1,2 Department of Mathematics, Loyola College – 600 034, Chennai, India
3 R.M.D Engineering College, Kavarapettai, Thiruvallur – 601 206, India
Abstract
Let = , be a graph with vertex set and edge set . Let denote the diameter of and
, denote the distance between the vertices
and in . An antipodal labeling of with diameter
is a function that assigns to each vertex , a positive integer , such that , +
, for all , . The span of an antipodal labeling is : ,
(). The antipodal number for , denoted by , is the minimum span of all antipodal labelings of . Determining the antipodal number of a graph G is an NPcomplete problem. In this paper we determine the antipodal number of circulant graphs .
Keywords
Labeling, radio antipodal numbering, diameter, circulant.

Introduction
Let G be a connected graph and let be an integer, 1. A radio – labeling of is an assignment of positive integers to the vertices of
such that , + + 1 for every two distinct vertices and of, where
, is the distance between any two vertices and
of . The span of such a function, denoted by sp = : , () . Radio
labeling was motivated by the frequency assignment problem [3]. The maximum distance
labeling is a oneto one function, while in an antipodal labeling, two vertices of distance apart may receive the same label.
The antipodal labeling for graphs was first studied by Chartrand et al.[8], in which, among other results, general bounds of were obtained. Khennoufa and Togni [10] determined the exact value of for paths . The antipodal labeling for cycles was studied in [4], in which lower bounds for are obtained. In addition, the bound for the case 2 4 was proved to be the exact value of
, and the bound for the case 1 4 was conjectured to be the exact value as well [7]. Justie Sutzu Juan and Daphne DerFen Liu [9] confirmed the conjecture mentioned above. Moreover they determined the value of for the case
3 4 and also for the case 0 4 .
They improve the known lower bound [4] and give an upper bound. They also conjecture that the upper bound is sharp.
In this paper we obtain an upper bound for the radio antipodal number of the Circulant graphs.
2
2
Definition An undirected circulant graph denoted by G(n; {1, 2 j}), 1 j n , n 3, is defined as a graph with vertex set
V {0,1 n 1}
and edge set
E {(i, j) : j s(mod n), s {1, 2,, j}}.
For our convenience we take the vertex set V as
among all pairs of vetices in G is the diameter of G.
{v1, v2
. . .
vn }
in clockwise order.
The radio labeling is a radio – labeling when
= . When = 1, a radio – labeling is called a radio antipodal labeling. In otherwords, an antipodal labeling for a graph G is a function ,: 0,1,2, such that , +
. The radio antipodal number for G, denoted by , is the minimum span of an antipodal labeling admitted by G. A radio
The diameters of certain classes of circulant graphs which are going to be discussed in this are given below:
2
2
1. Diameter of G n;1, 2 … n 1 is 2 .

If n 0 (mod 4) , then the diameter of
2
2
4
4
G n;1, n is n .
d(u, w) f (u) f (w) 1 (k m) 2,

If n 0 (mod 3) , then the diameter of
since k m.
3
3
G n; 1, n
is n 1.
Case 3: If
u vk
and
6
6
2
2

If n 0 (mod 10) , then the diameter of
w v n m
, 1 k n , 1 m n ,
then
2 2
2 2
5
5
G n; 1, n
is n 2.
either
d(u, w) 1
and
f (u) f (w) 1 or
10
10
Theorem: The radio antipodal number of the
d(u, w) 2
and f (u) f (w) 0.
In both
2
2
circulant graph G n;1, 2 … n 1 is given by
cases, we have d(u, w)
f (u) f (w) 2.
n n
Thus d(u, w) f (u) f (w) 2 for all
an G n; 1, 2 … 2 1 2 .
u, wG n;1, 2 … n 1.
2
Therefore f is a radio antipodal labeling and
Proof: Let
2
2
V G n;1, 2 … n 1 {v1, v2
. . .
vn } .
an(G) n.
2
2
an G n;1, 2 … n 1 n
an( f ).
Define a mapping
f :{v1, v2 … vn} N as
Hence the radio antipodal number of
follows:
2
2
f (vi ) i, i 1, 2 … n ,
G n;1, 2 … n 1
n
.
.
is 2
f v n
i, i 1, 2 … n .
2
2
See figure 1
Theorem: The radio antipodal number of
v11
2 i 2
v1 1
v2 2
5
G n; 1, n ,
2
2
satisfies
n 0(mod 4), n 16,
v3 3
n n n
v10 4
an G n; 1, 2 2 1 4 2.
v4 4
v9 3
Proof: We partition the vertex set
v5 5
V {v1, v2 … vn} into four disjoint sets
v8 2
v6 6
v7 1
V1 , V2 , V3 and V4 . Let V1 v1, v2 … vn ,
Figure 1 A circulant graph of G(11,{1,2,3,4})
First we claim that f is a radio antipodal labeling.
Case 1: If u vk and
4
4 4 2
4 4 2
V2 vn 1, vn 2 … vn ,
2 2 2
2 2 2
V3 vn 1, vn 2 … v3n and
w vm , 1 k m n , then d(u, w) 1,
V v n , v n … v . See figure 2.
2
f (u) k and f (w) m . Hence
4 32 1 32 2 n
d(u, w) f (u) f (w) 1 (k m) 2,
Define a mapping f : V G n;1, n N as
2
2
since k m.
follows:
Case 2: If
u v n k and
4 8
4 8
f (v2i1 ) (i 1) n 21, i 1, 2 … n ,
2
f (v ) n i 1 n 2, i 1, 2 … n ,
w v n m
, 1 k m n ,
2
2
then
f (u) k
2i 8 4
8
2
f vn i 1 n 21, i 1, 2 … n ,
and
f (w) m
and
d(u, w) 1.
Therefore
4 2i1 4
8
Subcase 2.1: If
u v2l 1
and
w vn 2l 1,
f vn n i 1 n 2, i 1, 2 … n ,
8
8
4
4
4
4 2i
8 4
8
1 l n ,
then
d u, w n
and
f v n i 1 n 21, i 1, 2 … n ,
8
8
f u f w 0. Therefore
n2 n 2i3 4 4
8
d u, w f u f w n 0 n .
4 4
4 4
n2 n 2i2 8 4 4
8
Subcase 2.2: If u v and w v
such that
f v
8
n n i 1 n 2, i 1, 2 … n ,
n n n
1 l n ,
2l
1 m n ,
n 2m
4
4
l m 1
then
f vn2(i1) 4 i 1 4 21, i 1, 2 … 8 ,
8 4 4 8
8 4 4 8
f vn(2i1) n n i 1 n 2, i 1, 2 … n .
8
d u, w 2
Therefore
and
8
4
4
f u f w n 2.
4 4
4 4
We claim that
d u, w
f u f w n
for
d u, w
f u f w 2 n n .
4
4
2
2
all u, wV (G n;1, n.
Subcase 2.3: If u vl
and w vm ,l m,
Case 1:
u, wV1
l m 1, then
d u, w 1
f u f 
w 
n 1. There 

d u, w 
f u 

n 4 
f u f 
w 
n 1. There 

d u, w 
f u 

n 4 
4
and
fore
Subcase 1.1: If
u v2l 1
and
w v2m1, .
8
8
1 l m n , then
Similarly we can prove the remaining cases as in case
4
4
d u, w 2, f u l 1 n 21
and
2. Hence f is a radio antipodal labeling and that
f w m 1 n 21. Therefore
n n n
n n n
an G n; 1, 1 2 .
4 4
4 4
4
2 2 4
d u, w
f u f w 2 l m n 2 n .
v19
v20
v1 v2
v3
23
35
1 13
5
Subcase 1.2: If
u v2l
and
w v2m ,
v18
v4 27 17
8
8
1 l m n ,
then
d u, w 2,
v17
v16
v5 39 9
v6 31 2
f u n l 1 n 2
and
v15 24
8 4
v7 14
f w n m 1 n 2.
Therefore
v14
v8 36 6
8 4
v13
v9 28 18
d u, w
f u f w 2 l m n 2 n .
v12
v11
v10
40 32 10
4 4 Figure 2 A circulant graph with diameter 5
Subcase 1.3: If
u v2l 1
and
w v2m ,
then
f w n m 1 n 2.
f w n m 1 n 2.
d u, w 2.
Also
f u l 1 n 21
Theorem: The radio antipodal number of
3
Therefore
3
Therefore
4 G n; 1, n ,
n 0 (mod 3)
satisfies
and
and
8 4
n
n n 1 n , if n is even
an G n; 1,
6 2
12 .
d u, w f u f w 2 l 1 n 21 n m 1 n 2 2 n 2 n .
3
( n 1) n1 1, if n is odd
4 8
Similarly we can prove for the cases if
4 4 4
u, wV2 ,
6 2
Proof: We partition the vertex set
2
2
or u, wV3 or u, wV4 .
V {v1, v2 … vn} into two sets V1 and V2 ,
Case 2: u V1 and wV2
where V1 v1, v2 … v n and
2 2
2 2
V2 v n 1, v n 2 … vn .
Proof: We partition the vertex set
We provide the labeling both when n is even and odd. See figure 3 and 4
V {v1, v2 … vn}
into two sets V1 and V2 ,
v17
v18
v1 v2
v3
1 4
26 7
23
where
V1 v1, v2 … v n
and
v16 v15
v4
v5 20
17
10
13 V2
v n 1
, v n 2
… vn
2
2
. See figure 5
v14 v13
v12
v6
14
v7
11
v8 8
2 2
16
19 Define a mapping
5
5
22 as follows:
f : V G n;1, n N
v11
v10 v9
5 25
f (v ) n 1(i 1) 1, i 1, 2 n ,
2
diameter 4
i
f vn
10 2
n 1(i 1) 1, i 1, 2 n .
Figure 3 A circulant graph of G(18,{1,2,3,4,5,6}) with
2 i
10 2
Case 1: n is even Define a mapping f
3
3
follows:
: V G n;1, n N as
proof is similar.
v20 v1 v2
v19 v3
1
28 4
25 7
f (v ) n (i 1) 1, i 1, 2 n ,
v18
v4 22 10
i
f v
2
2
6 2
n (i 1) n 1, i 1, 2 n .
v17
v16
v5 19 13
v6 16 16
n i 6
12
2 v15
v7 13 19
Case 2: n is odd
v14
v8 10 22
v19
v20
v21 v1
v2
v3
v
29 1
26 4
7
23
v13
v12
v11
v9
v10
25
7
4 1 28
v18
4 20 10
Figure 5 A circulant graph of G(20,{1,2,3,4})
v17 v5 17 13
v16 v6 14 16
v15 v7 11
v14 v8 8
19 4. Conclusion
22 The study of radio antipodal number of graphs has gained momentum in recent years. Very few graphs
v13
v12
v11
v9
v10
5 25
2 31 28
have been proved to have radio antipodal labeling
Figure 4 A circulant graph of G(21,{1,27}) with diameter 4
3
3
Define a mapping f : V G n;1, n N as
follows:
6 2
6 2
f (vi ) ( n 1)(i 1) 1, i 1, 2 n1 ,
that attains the radio antipodal number. In this paper we have determined the bounds of the radio antipodal number of the lobster and extended mesh. Further study is taken up for various other classes of graphs.

References
f vn1
( n 1)(i 1) n , i 1, 2 n1 .

T. Calamoneri and R. Petreschi, L(2,1)labeling of planar graphs, ACM (2001),2833.
2 i 6 12
proof is similar to the above class.
Theorem: The radio antipodal number of
5
5
G n;1, n, n 0 (mod 10) satisfies
2

G.J.Chang and C.Lu, Distance two labeling of
graphs, European Journal of Combinatorics,24 (2003),5358.

G.Chartrand, D.Erwin, and P.Zhang, Radio kcolorings of Paths,Disscus Math.Graph Theory,24 (2004), 521

G.Chartrand, D.Erwin, and P.Zhang, Radio antipodal
colorings of cycles, Congressus Numerantium, 144 (2000).
n
n
5 20
5 20
an G n; 1,
n (n 8).

G.Chartrand, D.Erwin, and P.Zhang, Radio antipodal
colorings of graphs, Math. Bohem.,127 (2002), 57 69.

G.Chartand,Erwin, Zhang,Kalamazoo Radio antipodal coloring of graphs May 12,2000,.

G.Chartrand,D.Erwin, and .Zhang, Radio labeling of graphs,Bull. Inst. Combin.Appl.,33(2001),7785.

Justie Sutzu Juan and Daphne DerFen Liu,, Antipodal labeling for Cycles, Dec 12, 2006.

R.Khennoufa and O.Tongni,A note on radio antipodal colouring of paths,Math.Bohem.,130(2005).

Mustapha Kchikech, Riadh Khennoufa and Olivier Tongi, Linear and cyclic radio klabelings of Trees,Discussiones Mathematicae Graph theory, (2007).

G.Ringel, Theory of Graphs and its applications,Proceedings of the Symposium Smolenice 1963,Prague Publ.House of Czechoslovak Academy
of Science,pages 162, 1964.

A.Rosa, Cyclic Steiner triple systems and labeling of triangular cacti, Scientia Vol 1, pages 8795,988.

Bharati Rajan, Indra Rajasingh,Kins Yenoke, Paul Manuel, Radio number of graphs with small diameter, International Journal of Mathematics and
Computer Science, Vol 2, pages 209220, 2007.

Bharati Rajan, Indra Rajasingh,Jude Annie Cynthia, Minimum metric dimension of mesh derived architectures, International conference of Mathematics and Computer Science, Vol 1, pages 153156, 2009.
