DOI : 10.17577/IJERTV2IS2261
- Open Access
- Total Downloads : 755
- Authors : Priyam Vashishta
- Paper ID : IJERTV2IS2261
- Volume & Issue : Volume 02, Issue 02 (February 2013)
- Published (First Online): 28-02-2013
- ISSN (Online) : 2278-0181
- Publisher Name : IJERT
- License:
This work is licensed under a Creative Commons Attribution 4.0 International License
The L(2,1) – Labeling of Dragon and Armed Crown Graphs
Priyam Vashishta
Abstract
An L(2,1)-labeling of a graph G is a function f from
(1)
(2)
f x f y
f x f y
2 if d x, y 1
1 if d x, y 2
the vertex set V(G) to the set of all nonnegative
A L(2,1) – labeling in which no label is greater than
integers such that
and f x f y
f x f y
-
if d x, y
-
if d x, y 1
2 . The L(2,1)-
k is called a k – L(2,1) – labeling. The smallest number k such that G has a k – L(2,1) labeling is called the L(2,1) labeling number of G and is
labeling number of G, denoted by G or , is the smallest number k such that max f v : v V G k . In this paper I will
completely determine G -number for dragon and armed crown graphs.
key – words:
L(2,1)-labeling, -number , dragon, armed crown.
-
Introduction
denoted by G or . The L(2,1) labeling has
been studied extensively in recent past by many researchers like Yeh [8], Sakai [6], Georges, Mauro and Whittlesey [3], Georges and Mauro [2], and Vaidya, Vihol, Dani and Bantva[7].
Throughout this work, I will consider the finite, connected and undirected simple graph
G V G , E G . Following is the brief summary
of definitions and information which are prerequisites for the present work.
Definition 1.2: A Dragon, Dn m is a graph in
The channel assignment problem is to assign a channel (non negative integer) to each TV or radio transmitters located at various places such that communication do not interfere. In 1980, Hale [5] introduced the notion of T coloring of a graph. He formulated the channel assignment problem as a graph coloring problem.
In 1988, Roberts proposed a variation of the channel assignment problem in which close transmitters must receive channels that are at least two apart. In a graph model of this problem, the transmitters are represented by the vertices of a graph. Two vertices are very close if they are adjacent in the graph and close if they are at a distance two apart in the graph. In [4], Griggs and Yen motivated by the above problem proposed by Roberts introduced L(2,1) labeling.
Definition 1.1: An L(2,1) labeling (or distance two labeling) of a graph G V G , E G is a
which path Pm is attached to any vertex of cycle Cn . Definition 1.3: An armed crown, Cn Pm is a graph in which path Pm is attached at each vertex of
the cycle Cn .
Proposition 1.4: [4] The -number of a star K1,
is 1, where is the maximum degree.
Proposition 1.5: [4] The -number of a complete graph Kn is 2n 2 .
Proposition 1.6: [1] H G , for any subgraph H of a graph G.
-
Main Result
Theorem 2.1: The -number of a Dragon
Dn m for n 3 and m 1 is 4.
Proof: Let v0 , v1 ,, vn 1 be the vertices of the
function f from vertex set G V G , E G to the
cycle of
Dn m such that vi is adjacent to
vi 1 ,
set of all nonnegative integers such that the following conditions are satisfied:
0 i n 2 and v0 is adjacent to vn 1 . Also, let
u0 ,u1,,um 1 be the vertices of the path or tail of
Dn m such that u j
is adjacent to
uj 1 , 2 4
0 j m
2 and u0
is adjacent to v0 . The graph
K1,3
is a subgraph of
Dn m and hence by
Proposition 1.4 and 1.6
Dn m
4 . Now define
0
4 1 3 0
f :V Dn m
0,1, 2, 3, 4
as follows. We start
vertex labeling from v0 . 4 2
-
n
0mod 3
Figure – 1
0 , i
0 mod 3
Theorem 2.3: The -number of an armed crown
f vi
2 , i
1mod 3
Cn Pm for n
3 and m
-
is 5.
4 , i
2 mod 3
Proof: Let
v0 , v1 ,, vn 1
be the vertices of the
and
cycle of
Cn Pm
such that vi
is adjacent to
vi 1 ,
3 , j
0 mod 4
0 i n
-
and v0
is adjacent to
vn 1 . Also, let
1 , j
f u
1mod 4
u0 ,u1,,um 1 be the vertices of the path which is
j 4 , j
2 mod 4
attached to every vertex of Cn such that
u j is
0 , j
3 mod 4
adjacent to uj 1 , 0 j m 2
. We denote the
-
-
n
1mod 3
then redefine the above f at
vertices of the path adjacent to the vertex vi
, , as
vn 4 ,vn 3 ,vn 2 ,vn 1 as
ui 0 , ui1 ,, ui m 1
where
ui 0
adjacent to vi
0 , i n 4
0 i n
1 . The graph
K1,3
is a subgraph of
f vi
3 , i n 3
1 , i n 2
Dn m and hence by Proposition 1.4 and 1.6
4 , i n 1
Cn Pm 4
. Now define
and
f :V Cn Pm
0,1, 2,3, 4,5
as follows.
3 , j
0 mod 4
(1)
n 0mod 3
f u j
1 , j
4 , j
0 , j
1mod 4
2 mod 4
3 mod 4
f vi
5
, j
0 mod 3
f
u
3
, j
1mod 3
0
, j
2 mod 3
f
v
2, i
1m
od 3
5
, j
0 mod 3
f
uij
0
, j
1mod 3
2
, j
2 mod 3
an
f
d
vi
4, i 2 mod 3
1 , j 0 mod 3
f
uij
3 , j 1mod 3
5 , j 2 mod 3
5
, j
0 mod 3
f
u
3
, j
1mod 3
0
, j
2 mod 3
f
v
2, i
1m
od 3
5
, j
0 mod 3
f
uij
0
, j
1mod 3
2
, j
2 mod 3
an
f
d
vi
4, i 2 mod 3
1 , j 0 mod 3
f
uij
3 , j 1mod 3
5 , j 2 mod 3
ij
0, i
0 mod 3
-
n
2mod 3
then redefine f in (1) at vn 2
and vn 1 as
i
f vi
1 , i n 2
3 , i n 1
and
f u j
Hence,
4 , j
1 , j
3 , j
0 , j
Dn m
0 mod 4
1mod 4
2 mod 4
3 mod 4
4 .
Illustration 2.2: In the following Figure-1 the
L(2,1)-labeling of graph D6 4 is shown.
(2)
n 1mod 3
then redefine the above f at
vn 4 ,vn 3 ,vn 2 ,vn 1 and the corresponding uij 's as
f vi 0, i n 4 ,
5
, j
0 mod 3
2
f
uij
3
, j
1mod 3
0
0
, j
2 mod 3
5
f
vi
3, i
n
3 ,
2
5
, j
0 mod 3
4
f
uij
2
, j
1mod 3
0
, j
2 mod 3
0
3
5
0
5
, j
0 mod 3
2
f
uij
3
, j
1mod 3
0
0
, j
2 mod 3
5
f
vi
3, i
n
3 ,
2
5
, j
0 mod 3
4
f
uij
2
, j
1mod 3
0
, j
2 mod 3
0
3
5
0
3 5
0
f vi
f u j
and
f vi
f uij
1, i n
5 , j
2 , j
0 , j
4, i n
2 , j
5 , j
0 , j
2 ,
0 mod 3
1mod 3
2 mod 3
1 ,
0 mod 3
1mod 3
2 mod 3
3 1
2
2
0 5 5 0
2 Figure 2
-
-
Conclusion
Here I have proved that the number of a dragon is 4 and the number of an armed crown is 5.
-
References
(3) n 2mod 3 then redefine f in (1) at vn 2
and vn 1 and the corresponding uij 's as
-
G. J. Chang, and D. Kuo, The L(2,1) -labeling problem on graphs, SIAM J. Discrete Math. 9(2), 1996,
f vi
f uij
f vi
f uij
and
f vi
f uij
4, i n
0 , j
3 , j
5 , j
1, i n
5 , j
0 , j
2 , j
3, i n
5 , j
0 , j
2 , j
3 ,
0 mod 3
1mod 3
2 mod 3
2 ,
0 mod 3
1mod 3
2 mod 3
1 ,
0 mod 3
1mod 3
2 mod 3
pp.309-316.
-
J. Georges, and D. Mauro, Generalized vertex labelings with a condition at distance two, Congr. Numer. 109, 1995, pp.141-159.
-
J. Georges, D. Mauro, and M. Whittlesey, Relating path covering to vertex labelings with a condition at distance two, Discrete Math. 135, 1994, pp.103-111.
-
J. R. Griggs, and R. K. Yeh, Labeling graphs with a condition at distance 2, SIAM J. Discrete Math. 5, 1992, pp.586-595.
-
W. K. Hale, Frequency assignment: Theory and applications, Proc. IEEE, 68, 1980, pp.1497-1514.
-
D. Sakai, Labeling chordal graphs: Distance two condition, SIAM J. Discrete Math. 7(1), 1994, pp.133-140.
-
S. K. Vaidya, P. L. Vihol, N. A. Dani, and D. D. Bantva, L(2,1) – labeling in the context of some graph operations, Journal of Mathematics Research, 2(3), 2010, pp. 109-119.
-
R. K. Yeh, Labeling graphs with a condition at distance two, Ph. D. Thesis, Dept. of Math., University of South Carolina, Columbia, SC, 1990.
Hence,
Dn m 5 .
Illustration 2.4: In the following Figure-2 the
L(2,1)-labeling of graph C5 P3 is shown.