Radio Antipodal Number of Circulant Graphs

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 NP-complete problem. In this paper we determine the antipodal number of circulant graphs .

Keywords

Labeling, radio antipodal numbering, diameter, circulant.

1. 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 one-to 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 Su-tzu Juan and Daphne Der-Fen 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 .

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,

3. 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

4. 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	f w		n 4

f u f	w	n 1. There
d u, w	f u	f w		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.

1. References

   f vn1

   ( n 1)(i 1) n , i 1, 2 n1 .

   1. T. Calamoneri and R. Petreschi, L(2,1)-labeling of planar graphs, ACM (2001),28-33.

      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

   2. G.J.Chang and C.Lu, Distance two labeling of

      graphs, European Journal of Combinatorics,24 (2003),53-58.

   3. G.Chartrand, D.Erwin, and P.Zhang, Radio k-colorings of Paths,Disscus Math.Graph Theory,24 (2004), 5-21

   4. 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).

   5. G.Chartrand, D.Erwin, and P.Zhang, Radio antipodal

      colorings of graphs, Math. Bohem.,127 (2002), 57- 69.

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

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

   8. Justie Su-tzu Juan and Daphne Der-Fen Liu,, Antipodal labeling for Cycles, Dec 12, 2006.

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

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

   11. 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.

   12. A.Rosa, Cyclic Steiner triple systems and labeling of triangular cacti, Scientia Vol 1, pages 87-95,988.

   13. 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 209-220, 2007.

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