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

- Received : March 24, 2014
- Accepted : July 05, 2014
- Published : January 30, 2015

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

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.
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
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
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}
, ...
v_{n}
} in clockwise order.
Remark 1.1.
The diameter of class of circulant graphs which are going to be discusse
d_{i}
n this paper is:
In this paper, radio and radio antipodal numbers for the class of circulant graphs
G
(4
k
+ 2 : {1, 2}) are computed.
Theorem 2.1.
The radio number of the circulant graphs G
(4
k
+ 2 : {1, 2})
is given by
Theorem 2.2.
The radio antipodal number of the circulant graphs G
(4
k
+ 2; {1, 2})
is given by
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
i^{th}
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}),
Proof
. By Lemma 3.1,
d
(
v
_{1}
,
v
_{2}
_{k}
_{+2}
) =
k
+ 1 =
d
. Case(i): For odd
k
.
and a path of length
between
v
_{2}
_{k}
_{+2}
and
v
_{3}
_{k}
_{+3}
is
and
as
This implies that
Case (ii): For even
k
.
and a path of length
and 1 between
v
_{2}
_{k}
_{+2}
and
v
_{3}
_{k}
_{+3}
is
Also,
because
Thus,
Therefore, for any three vertices
u, v, w
on the graphs
G
(4
k
+ 2; {1, 2}),
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
{
x_{i}
: 1 ≤
i
≤ 4
k
+ 2}
be the ordering of V
(
G
(4
k
+ 2; {1, 2}))
such that f
(
x_{i}
) <
f
(
x_{i}
_{+1}
)
for all
1 ≤
i
≤ 4
k
+ 1,
then
Proof
. By definition,
Summing these inequalities yields
Furthermore, by Lemma 4,
d
(
u, v
) +
d
(
v, w
) +
d
(
w, u
) ≤ 2
d
, so we have
As
d
= diam(
G
(4
k
+ 2; {1, 2})) =
k
+ 1, it follows that
Thus
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
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
(
x_{i}
) <
f
(
x_{i}
_{+1}
) defined by
f
(
x
_{1}
) = 0 and, set
d_{i}
=
d
(
x_{i}
,
x_{i}
_{+1}
) and
f_{i}
=
f
(
x_{i}
_{+1}
) −
f
(
x_{i}
). Then
f_{i}
≥
d
+1−
d_{i}
for all
i
. By Lemma 5, the span of a distance labeling for
G
(4
k
+2; {1, 2}) is
Thus,
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
the color gap sequence
and the vertex gap sequence
T
For odd
k
. The distance gap sequence is given by:
The color gap sequence
F
is given by:
For even
k
. The distance gap sequence is given by:
The color gap sequence
F
is given by:
The vertex gap sequence for all values of
k
is:
Where
t_{i}
denotes number of vertices between
x_{i}
and
x_{i}
_{+1}
.
Let
π
: {1, 2, 3, ..., 4
k
+ 2} → {1, 2, 3, ..., 4
k
+ 2} be defined by
π
(1) = 1 and
Let
x_{i}
=
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
(
x_{i}
_{+1}
) =
f
(
x_{i}
) +
f_{i}
. Then for
i
= 1, 2, 3, ..., 2
k
+ 2,
and for
i
= 1, 2, ...2
k
+ 2,
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
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
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:
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
which is impossible when
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
As
k
is even and g.c.d.(4
k
+ 2,
k
) = 2 it follows that
Which is not possible.
When
k
is even, then span of
f
is equal to:
Radio labeling and ordinary labeling of G (10; {1, 2})
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
{
x_{i}
: 1 ≤
i
≤ 4
k
+ 2}
be the ordering of V
(
G
(4
k
+ 2; {1, 2}))
such that f
(
x_{i}
) ≤
f
(
x_{i}
_{+1}
)
for all
1 ≤
i
≤ 4
k
+ 1,
then
Proof
. By definition,
f
(
x_{i}
_{+1}
) −
f
(
x_{i}
) ≥
d
−
d
(
x_{i}
_{+1}
,
x_{i}
),
f
(
x_{i}
_{+2}
) −
f
(
x_{i}
_{+1}
) ≥
d
−
d
(
x_{i}
_{+2}
,
x_{i}
_{+1}
) and
f
(
x_{i}
_{+2}
) −
f
(
x_{i}
) ≥
d
−
d
(
x_{i}
_{+2}
,
x_{i}
). Summing up these three in-equalities and by Lemma 4, we get
Thus,
Theorem 4.2.
The radio antipodal number of the circulant graphs G
(4
k
+ 2; {1, 2})
is given by
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
(
x_{i}
) ≤
f
(
x_{i}
_{+1}
) defined by
f
(
x
_{1}
) = 0 and, set
d_{i}
=
d
(
x_{i}
,
x_{i}
_{+1}
) and
f_{i}
=
f
(
x_{i}
_{+1}
)−
f
(
x_{i}
). Then
f_{i}
≥
d
−
d_{i}
for all
i
. By Lemma 7, the span of a distance labeling for
G
(4
k
+ 2; {1, 2}) is
Thus,
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:
For even
k
. The color gap sequence
F
is given by:
When
k
is odd, then span of
f
is equal to:
When
k
is even, then span of
f
is equal to:
Radio antipodal labeling and ordinary labeling of G (10; {1, 2})
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

1. Introduction

Let
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

2. Main results

The main theorems of this paper are:
PPT Slide

Lager Image

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(
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

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.
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

BIO

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

Citing 'ADIO AND RADIO ANTIPODAL LABELINGS FOR CIRCULANT GRAPHS G(4k + 2; {1, 2}) †
'

@article{ E1MCA9_2015_v33n1_2_173}
,title={ADIO AND RADIO ANTIPODAL LABELINGS FOR CIRCULANT GRAPHS G(4k + 2; {1, 2}) †}
,volume={1_2}
, url={http://dx.doi.org/10.14317/jami.2015.173}, DOI={10.14317/jami.2015.173}
, number= {1_2}
, journal={Journal of Applied Mathematics & Informatics}
, publisher={Korean Society of Computational and Applied Mathematics}
, author={NAZEER, SAIMA
and
KOUSAR, IMRANA
and
NAZEER, WAQAS}
, year={2015}
, month={Jan}