Advanced
ADIO AND RADIO ANTIPODAL LABELINGS FOR CIRCULANT GRAPHS G(4k + 2; {1, 2}) †
ADIO AND RADIO ANTIPODAL LABELINGS FOR CIRCULANT GRAPHS G(4k + 2; {1, 2}) †
Journal of Applied Mathematics & Informatics. 2015. Jan, 33(1_2): 173-183
Copyright © 2015, Korean Society of Computational and Applied Mathematics
  • Received : March 24, 2014
  • Accepted : July 05, 2014
  • Published : January 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
SAIMA NAZEER
IMRANA KOUSAR
WAQAS NAZEER

Abstract
A radio k -labeling f of a graph G is a function f from V ( G ) to Z + ∪ {0} such that d ( x, y ) + | f ( x ) − f ( y )| ≥ k + 1 for every two distinct vertices x and y of G , where d ( x, y ) is the distance between any two vertices x, y G . The span of a radio k -labeling f is denoted by sp ( f ) and defined as max{| f ( x ) − f ( y )| : x, y V ( G )}. The radio k -labeling is a radio labeling when k = diam( G ). In other words, a radio labeling is an injective function f : V ( G ) → Z + ∪ {0} such that for any pair of vertices x, y G . The radio number of G denoted by rn( G ), is the lowest span taken over all radio labelings of the graph. When k = diam( G ) − 1, a radio k - labeling is called a radio antipodal labeling. An antipodal labeling for a graph G is a function f : V ( G ) → {0, 1, 2, ...} such that d ( x, y ) + | f ( x ) − f ( y )| ≥ diam( G ) holds for all x, y G . The radio antipodal number for G denoted by an( G ), is the minimum span of an antipodal labeling admitted by G . In this paper, we investigate the exact value of the radio number and radio antipodal number for the circulant graphs G (4 k + 2; {1, 2}). AMS Mathematics Subject Classification : 05C12, 05C15, 05C78.
Keywords
1. Introduction
Let G be a connected graph with vertex set V ( G ) and edge set E ( G ) and let k be an integer, k ≥ 1. A radio k -labeling f of G is an assignment of non negative integers to the vertices of G such that | f ( x )− f ( y )| ≥ k +1− d ( x, y ), where d ( x, y ) denotes the distance for every two distinct vertices x and y of G . The span of the function f is max{| f ( x ) − f ( y )| : x, y V ( G )} and denoted by sp( f ). The radio k -labeling number of G is the smallest span among all radio k -labelings of G. Chartrand et al. [1] was the first, who studied the radio k -labeling number for paths, where lower and upper bounds were given. These bounds have been improved by Kchikech et al. [7] . The radio k -labeling becomes a radio labeling for k = diam( G ). A radio labeling is a function from the vertices of the graph to some subset of non negative integers. The task of radio labeling is to assign to each station a non negative smallest integer such that the disturbance in the nearest channel should be minimized. In 1980 [5] , Hale presented this channel assignment for the very first time by relating it to the theory of graphs.
Multilevel distance labeling problem was introduced by Chartrand et al. [4] in 2001. A radio labeling is an injective function f : V ( G ) → Z + ∪ {0} satisfying the condition
PPT Slide
Lager Image
for any pair of vertices x, y in G . Where d ( x, y ) is the distance between any distinct pair of vertices in G , which is the length of the shortest path between them. The largest number that f maps to a vertex of a graph is the span of labeling f . Radio number of G is the minimum span taken over all radio labelings of G and is denoted by rn( G ). When k = diam( G ) − 1, a radio k - labeling is referred to as a (radio) antipodal labeling, because only antipodal vertices can have the same label. The minimum span of an antipodal labeling is called the antipodal number, denoted by an( G ). In [1] and [2] , Chartrand et al. were studied the radio antipodal labeling for path and cycle. In [3] , Chartrand et al. gave general bounds for the antipodal number of a graph. The exact value of the radio antipodal number of path was found in [9] . Justic and Liu have computed the radio antipodal number of cycles. In [10] , by using a generalization of binary Gray codes the radio antipodal number and the radio number of the hypercube are determined.
An undirected circulant graph denoted by G ( n ; ±{1, 2, ..., j }) where
PPT Slide
Lager Image
is defined as a graph with vertex set V = {0, 1, 2, ... n − 1} and an edge set E = {( i, j ) : | j i | ≡ s (mod n ), s ∈ {1, 2, ..., j }}. For the sake of simplicity, take the vertex set as { v 1 , v 2 , ... vn } in clockwise order.
Remark 1.1. The diameter of class of circulant graphs which are going to be discusse di n this paper is:
PPT Slide
Lager Image
In this paper, radio and radio antipodal numbers for the class of circulant graphs G (4 k + 2 : {1, 2}) are computed.
2. Main results
The main theorems of this paper are:
Theorem 2.1. The radio number of the circulant graphs G (4 k + 2 : {1, 2}) is given by
PPT Slide
Lager Image
Theorem 2.2. The radio antipodal number of the circulant graphs G (4 k + 2; {1, 2}) is given by
PPT Slide
Lager Image
3. Radio number forG(4k+ 2; {1, 2})
In this section, we prove the Theorem 1 in two steps. First we provide a lower bound for rn( G (4 k + 2; {1, 2})) then define a multilevel distance labeling of ( G (4 k + 2; {1, 2})) with span equal to the lower bound, thus determining the radio number of ( G (4 k + 2; {1, 2})).
3.1. Lower bound for G (4 k + 2; {1, 2}). The lower bound for the radio number of G (4 k + 2; {1, 2}) is determined in following way. First examine the maximum possible sum of the pairwise distance between any three vertices of ( G (4 k + 2; {1, 2})) and use this maximum sum to compute a minimum possible gap between the ith and ( i + 2) nd largest label. Then provides a lower bound for the span of any labeling by using 0 for the smallest label and considering the size of gap into account.
Lemma 3.1. For each vertex on the graph G (4 k + 2; {1, 2}) there is exactly one vertex at a distance diameter d, of the graph G .
Proof . We show that d ( v 1 , v 2 k +2 ) = k + 1 = d . The path from v 1 to v 2 k +2 is of length k + 1 as v 1 v 2(1)+1 v 2(2)+1 → ... → v 2( k )+1 v 2( k )+1+1 . □
The following Lemma provides a maximum possible sum of the pairwise distances between any three vertices of G (4 k + 2; {1, 2}).
Lemma 3.2. For any three vertices u, v, w on the graphs G (4 k + 2; {1, 2}),
PPT Slide
Lager Image
Proof . By Lemma 3.1, d ( v 1 , v 2 k +2 ) = k + 1 = d . Case(i): For odd k .
PPT Slide
Lager Image
and a path of length
PPT Slide
Lager Image
between v 2 k +2 and v 3 k +3 is
PPT Slide
Lager Image
and
PPT Slide
Lager Image
as
PPT Slide
Lager Image
This implies that
PPT Slide
Lager Image
Case (ii): For even k .
PPT Slide
Lager Image
and a path of length
PPT Slide
Lager Image
and 1 between v 2 k +2 and v 3 k +3 is
PPT Slide
Lager Image
Also,
PPT Slide
Lager Image
because
PPT Slide
Lager Image
Thus,
PPT Slide
Lager Image
Therefore, for any three vertices u, v, w on the graphs G (4 k + 2; {1, 2}),
PPT Slide
Lager Image
The minimum distance between every other label (arranged in increasing order) in a multi-level distance labeling (or radio labeling) of G (4 k + 2; {1, 2}) is determined by using this maximum possible sum of the pairwise distances between any three vertices of G (4 k + 2; {1, 2}) together with the radio condition.
Lemma 3.3. Let f be radio labeling for V ( G (4 k + 2; {1, 2})), where { xi : 1 ≤ i ≤ 4 k + 2} be the ordering of V ( G (4 k + 2; {1, 2})) such that f ( xi ) < f ( xi +1 ) for all 1 ≤ i ≤ 4 k + 1, then
PPT Slide
Lager Image
Proof . By definition,
PPT Slide
Lager Image
Summing these inequalities yields
PPT Slide
Lager Image
Furthermore, by Lemma 4, d ( u, v ) + d ( v, w ) + d ( w, u ) ≤ 2 d , so we have
PPT Slide
Lager Image
As d = diam( G (4 k + 2; {1, 2})) = k + 1, it follows that
PPT Slide
Lager Image
Thus
PPT Slide
Lager Image
The above Lemma makes it possible to calculate the minimum possible span of a radio labeling of G (4 k + 2; {1, 2}).
Theorem 3.4. The radio number of the circulant graphs G (4 k + 2; {1, 2}) satisfies
PPT Slide
Lager Image
Proof . Let f be a distance labeling for G (4 k +2; {1, 2}) and { x 1 , x 2 , x 3 , ..., x 4 k +2 } be the ordering of vertices of G (4 k + 2; {1, 2}), such that f ( xi ) < f ( xi +1 ) defined by f ( x 1 ) = 0 and, set di = d ( xi , xi +1 ) and fi = f ( xi +1 ) − f ( xi ). Then fi d +1− di for all i . By Lemma 5, the span of a distance labeling for G (4 k +2; {1, 2}) is
PPT Slide
Lager Image
Thus,
PPT Slide
Lager Image
PPT Slide
Lager Image
Radio labeling and ordinary labeling of G(6; {1, 2})
3.2. Upper bound for rn G (4 k + 2; {1, 2}). To complete the proof of Theorem 1, we find upper bound and show that this upper bound is equal to the lower bound for G (4 k + 2; {1, 2}). The labeling is generated by three sequences, the distance gap sequence
PPT Slide
Lager Image
the color gap sequence
PPT Slide
Lager Image
and the vertex gap sequence T
PPT Slide
Lager Image
For odd k . The distance gap sequence is given by:
PPT Slide
Lager Image
The color gap sequence F is given by:
PPT Slide
Lager Image
For even k . The distance gap sequence is given by:
PPT Slide
Lager Image
The color gap sequence F is given by:
PPT Slide
Lager Image
The vertex gap sequence for all values of k is:
PPT Slide
Lager Image
Where ti denotes number of vertices between xi and xi +1 .
Let π : {1, 2, 3, ..., 4 k + 2} → {1, 2, 3, ..., 4 k + 2} be defined by π (1) = 1 and
PPT Slide
Lager Image
Let xi = u π (i) for i = 1, 2, 3, ..., 4 k + 2. Then x 1 , x 2 , x 3 , ..., x 4 k +2 is an ordering of the vertices of G , assuming f ( x 1 ) = 0, f ( xi +1 ) = f ( xi ) + fi . Then for i = 1, 2, 3, ..., 2 k + 2,
PPT Slide
Lager Image
and for i = 1, 2, ...2 k + 2,
PPT Slide
Lager Image
We will show that each of the sequences given above, the corresponding π are permutations. For odd k , g.c.d.(4 k + 2, k ) = 1 and 3 k + 2 ≡ − k (mod 4 k + 2) implies that (3 k + 2)( i i ′) ≡ k ( i ′ − i ) ≢ 0 (mod 4 k + 2). Because if it does so then k ( i ′ − i ) ≡ k .0 (mod 4 k + 2) and i ′ − i ≡ 0 (mod 4 k + 2) which is impossible when
PPT Slide
Lager Image
Therefore π (2 i − 1) ≠ π (2 i ′ − 1), if i i ′. Similarly π (2 i ) ≠ π (2 i ′), if i i ′. If π (2 i ) = π (2 i ′ − 1), then we get
PPT Slide
Lager Image
As k is odd and g.c.d.(4 k + 2, k ) = 1 it follows that i ′ − i ≡ 0 (mod 4 k + 2). This implies that 4 k + 2 divides i ′ − i < 2 k + 1, which is not possible.
When k is odd, then span of f is equal to:
PPT Slide
Lager Image
For even k , g.c.d.(4 k + 2, k ) = 2 and 3 k + 2 ≡ − k (mod 4 k + 2) implies that (3 k + 2)( i i ′ ) ≡ k ( i ′ − i ) ≢ 0 (mod 4 k + 2). Because if it does so then k ( i ′ − i ) ≡ k .0 (mod 4 k + 2) and
PPT Slide
Lager Image
which is impossible when
PPT Slide
Lager Image
Therefore π (2 i − 1) ≠ π (2 i ′ − 1), if i i ′. Similarly π (2 i ) ≠ π (2 i ′), if i i ′. If π (2 i ) = π (2 i ′ − 1), then
PPT Slide
Lager Image
As k is even and g.c.d.(4 k + 2, k ) = 2 it follows that
PPT Slide
Lager Image
Which is not possible.
When k is even, then span of f is equal to:
PPT Slide
Lager Image
PPT Slide
Lager Image
Radio labeling and ordinary labeling of G(10; {1, 2})
4. Radio antipodal number forG(4k+ 2; {1, 2})
In this section, the lower and upper bound for the radio antipodal number are determined and have shown that these bounds are equal.
4.1. Lower bound for an ( G (4 k + 2; {1, 2}). The technique for finding the lower bound for an( G (4 k + 2; {1, 2}) is analogous to that of rn( G (4 k + 2; {1, 2}).
Lemma 4.1. Let f be radio antipodal labeling for V ( G (4 k + 2; {1, 2})), where { xi : 1 ≤ i ≤ 4 k + 2} be the ordering of V ( G (4 k + 2; {1, 2})) such that f ( xi ) ≤ f ( xi +1 ) for all 1 ≤ i ≤ 4 k + 1, then
PPT Slide
Lager Image
Proof . By definition, f ( xi +1 ) − f ( xi ) ≥ d d ( xi +1 , xi ), f ( xi +2 ) − f ( xi +1 ) ≥ d d ( xi +2 , xi +1 ) and f ( xi +2 ) − f ( xi ) ≥ d d ( xi +2 , xi ). Summing up these three in-equalities and by Lemma 4, we get
PPT Slide
Lager Image
Thus,
PPT Slide
Lager Image
Theorem 4.2. The radio antipodal number of the circulant graphs G (4 k + 2; {1, 2}) is given by
PPT Slide
Lager Image
Proof . Let f be a distance labeling for G (4 k +2; {1, 2}) and { x 1 , x 2 , x 3 , ..., x 4 k +2 } be the ordering of vertices of G (4 k + 2; {1, 2}), such that f ( xi ) ≤ f ( xi +1 ) defined by f ( x 1 ) = 0 and, set di = d ( xi , xi +1 ) and fi = f ( xi +1 )− f ( xi ). Then fi d di for all i . By Lemma 7, the span of a distance labeling for G (4 k + 2; {1, 2}) is
PPT Slide
Lager Image
Thus,
PPT Slide
Lager Image
PPT Slide
Lager Image
Radio antipodal labeling and ordinary labeling of G(6; {1, 2})
4.2. Upper bound for an ( G (4 k +2; {1, 2}). To complete the proof of Theorem 2, we find upper bound and show that this upper bound is same as the lower bound for an( G (4 k + 2; {1, 2})). The technique for an upper bound of an( G (4 k + 2; {1, 2}) is analogous to that of rn( G (4 k + 2; {1, 2}), with replacing the color gap sequence.
For odd k . The color gap sequence F is given by:
PPT Slide
Lager Image
For even k . The color gap sequence F is given by:
PPT Slide
Lager Image
When k is odd, then span of f is equal to:
PPT Slide
Lager Image
When k is even, then span of f is equal to:
PPT Slide
Lager Image
PPT Slide
Lager Image
Radio antipodal labeling and ordinary labeling of G(10; {1, 2})
BIO
Saima Nazeer received M.Sc. from University of the Punjab, Lahore-Pakistan, and Ph.D. at University of the Punjab, Lahore-Pakistan. She is currently assistant Professor at Lahore College for Women University, Lahore-Pakistan. Her research area is graph theory.
Department of Mathematics, Lahore College for Women University, Lahore-Pakistan.
e-mail: saimanazeer123@yahoo.com
Imrana Kousar received M.Sc. from University of the Punjab, Lahore-Pakistan, and Ph.D. from University of the Punjab, Lahore-Pakistan,. She is currently assistant Professor at Lahore College for Women University, Lahore-Pakistan. Her research area is graph theory.
Department of Mathematics, Lahore College for Women University, Lahore-Pakistan.
e-mail: imrana.kousar@hotmail.com
Waqas Nazeer received M.Sc. from University of the Punjab, Lahore-Pakistan, and Ph.D. from Abdus Salam School of Mathematical Sciences, GC University, Lahore-Pakistan. He is currently assistant Professor at University of Education Township Lahore. His research interests are functional analysis and graph theory.
Department of Mathematics, University of Education Township Lahore, Lahore-Pakistan.
e-mail: waqaster@yahoo.com
References
Chartrand G. , Nebesk’y L. , Zhang P. (2004) Radio k-colorings of paths Discussiones Mathematicae Graph Theory 24 5 - 21    DOI : 10.7151/dmgt.1209
Chartrand G. , Erwin D. , Zhang P. (2000) Radio antipodal colourings of cycles Congressus Numerantium 144 129 - 141
Chartrand G. , Erwin D. , Zhang P. (2002) Radio antipodal colourings of graphs Math. Bohemica 127 57 - 69
Chartrand G. , Erwin D. , Zhang P. , Harary F. (2001) Radio labelings of grphs Bull. Inst. Combin. appl. 33 77 - 85
aleHale W.K. (1980) Frequency assignment: theory and application Proc IEEE 68 1497 - 1514    DOI : 10.1109/PROC.1980.11899
Juan J.S. , Liu D.F. 2006 Antipodal labelings for cycles (Manuscript)
Kchikech M. , Khenoufa R. , Togni O. (2007) Linear and cyclic radio k-labelings of trees Discussiones Mathematicae Graph Theory 27 105 - 123    DOI : 10.7151/dmgt.1348
Kchikech M. , Khenoufa R. , Togni O. Radio k-labelings for cartesian products of graphs, Discussion Mathematicae Graph Theory.
Khennoufa R. , Togni O. (2005) A note on radio antipodal colourings of paths Math. Bohemica 130 277 - 282
Khennoufa R. , Togni O. (2011) The radio antipodal and radio numbers of the hypercube Ars Combinatoria 102 447 - 461
Liu D. , Zhu X. (2005) Multi-level distance labelings for paths and cycles SIAM J. Disc. Math. 19 610 - 621    DOI : 10.1137/S0895480102417768
Liu D. , Xie M. (2004) Radio number for square cycles Congr. Numerantium 169 105 - 125