ON k-GRACEFUL LABELING OF SOME GRAPHS†

Journal of Applied Mathematics & Informatics.
2016.
Jan,
34(1_2):
9-17

- Received : June 15, 2015
- Accepted : July 25, 2015
- Published : January 30, 2016

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

In this paper, it has been shown that the hairy cycle
C_{n}
⊙
rK
_{1}
,
n
≡ 3(
mod
4), the graph obtained by adding pendant edge to each pendant vertex of hairy cycle
C_{n}
⊙ 1
K
_{1}
,
n
≡ 0(
mod
4), double graph of path
P_{n}
and double graph of comb
P_{n}
⊙ 1
K
_{1}
are
k
-graceful.
AMS Mathematics Subject Classification : 05C78.
k
-graceful labeling is the generalization of graceful labeling that intro-duced by Slater
[14]
in 1982 and by Maheo and Thuillier
[10]
also in 1982. Let
G
(
V,E
) be a simple undirected graph with order
p
and size
q, k
be an arbitrary natural number, if there exist an injective mapping
f
:
V
(
G
) → {0, 1,...,
q
+
k
−1} that induces bijective mapping
f
^{∗}
:
E
(
G
) → {
k, k
+ 1,...,
q
+
k
− 1} where
f
^{∗}
(
u, v
) = |
f
(
u
) −
f
(
v
)| ∀ (
u, v
) ∈
E
(
G
) and
u, v
∈
V
(
G
) then
f
is called
k
-graceful labeling, while
f
^{∗}
is called an induced edges
k
-graceful labeling and the graph
G
is called
k
-graceful graph. Graphs that are
k
-graceful for all
k
are sometimes called arbitrarily graceful.
Maheo and Thuillier
[10]
have shown that cycle
C_{n}
is
k
-graceful if and only if either
n
≡ 0 or 1(
mod
4) with
k
even and
k
≤ (
n
− 1)/2 or
n
≡ 3(
mod
4) with
k
odd and
k
≤ (
n
^{2}
− 1)/2, while P. Pradhan and et al.
[11]
have shown that cycle
C_{n}
,
n
≡ 0(
mod
4) is
k
-graceful for all
k
∈
N
(set of natural numbers). Maheo and Thuillier
[10]
have also proved that the wheel graph
W
_{2k+1}
is
k
-graceful and conjecture that
W
_{2k}
is
k
-graceful when
k
≠ 3 or
k
≠ 4. This conjecture has proved by Liang, Sun and Xu
[8]
. Liang and Liu
[7]
have shown that
K_{m,n}
is
k
-graceful. Acharya
[1]
has shown that eulerian graph with
q
edges is
k
-graceful if either
q
≡ 0 or 1(
mod
4) with
k
even or
q
≡ 3(
mod
4) with
k
odd. Seoud and Elsakhawi
[12]
have shown that paths and ladders are
k
-graceful.
Jirimutu
[5]
has shown that the graph obtained from
K
_{1,n}
(
n
≥ 1) by attaching
r
≥ 2 edges at each vertex is
k
-graceful for all
k
≥ 2. After that Jirimutu, Bao and Kong
[6]
have shown that the graph obtained from
K
_{2,n}
(
n
≥ 2) and
K
_{3,n}
(
n
≥ 3) by attaching
r
≥ 2 edges at each vertex is
k
-graceful for all
k
≥ 2 and Siqinqimuge and Jirimutu
[13]
have proved that the graph obtained from
K
_{4,n}
(
n
≥ 4) by attaching
r
≥ 2 edges at each vertex is
k
-graceful for all
k
≥ 2. Deligen, Zhao and Jirimutu
[3]
have proved that the graph obtained from
K
_{5,n}
(
n
≥ 5) by attaching
r
≥ 2 edges at each vertex is
k
-graceful for all
k
≥ 2. Bu, Zhang and He
[2]
have shown that an even cycle with a fixed number of pendant edges adjoined to each vertex is
k
-graceful.
In the following section, it has been shown that the hairy cycle
C_{n}
⊙
rK
_{1}
,
n
≡ 3(
mod
4) is
k
-graceful and the graph obtained by adding pendant edge to pendant vertex of hairy cycle
C_{n}
⊙ 1
K
_{1}
,
n
≡ 0(
mod
4) is also
k
-graceful.
G
to a caterpillar is called hairy cycle. The corona of cycle
C_{n}
and
rK
_{1}
i.e.
C_{n}
⊙
rK
_{1}
is the example of hairy cycle.
Theorem 2.1.
The hairy cycle C_{n}
⊙
rK
_{1}
,
n
≡ 3(
mod
4)
is admits k-graceful labeling where k
≤
r
.
Proof
. Let
u_{i}
(
i
= 1, 2,...,
n
) be the cycle vertices of hairy cycle
C_{n}
⊙
rK
_{1}
and the vertices of the
r
-hanged edges connected to each
u_{i}
(
i
= 1, 2,...,
n
) are denoted by
u_{it}
(
t
= 1, 2,...,
r
).
Consider the map
f
:
V
(
C_{n}
⊙
rK
_{1}
) → {0, 1,...,
n
(
r
+1)+
k
−1} defined as follows:
and
It is easy to check that
f
is injective mapping from
V
(
C_{n}
⊙
rK
_{1}
) to {0, 1,...,
n
(
r
+1) +
k
− 1}. Now we prove that the induced mapping
f
^{∗}
:
E
(
C_{n}
⊙
rK
_{1}
) → {
k, k
+ 1,...,
n
(
r
+ 1) +
k
− 1} where
f
^{∗}
(
u, v
) = |
f
(
u
) −
f
(
v
)| is a bijective mapping for all edges (
u, v
) ∈
E
(
C_{n}
⊙
rK
_{1}
). Let
The edge label induced by
f
^{∗}
is as follows.
We tide up the elements of each set and have a union
So the induced mapping
f
^{∗}
is a bijective mapping from
V
(
C_{n}
⊙
rK
_{1}
) onto {
k, k
+ 1,...,
n
(
r
+ 1) +
k
− 1}. Thus, the hairy cycle
C_{n}
⊙
rK
_{1}
,
n
≡ 3(
mod
4) is admits
k
-graceful labeling. For example, 3-graceful labeling of hairy cycle
C
_{7}
⊙ 4
K
_{1}
, has shown in
Fig. 1
. □
3-graceful labeling of hairy cycle C _{7} ⊙ 4K _{1}
Theorem 2.2.
The graph obtained by adding pendant edge to each pendant vertex of hairy cycle C_{n}
⊙ 1
K
_{1}
,
n
≡ 0(
mod
4)
admits k-graceful labeling
.
Proof
. The order and size of the graph
G
obtained by adding pendant edge to each pendant vertex of hairy cycle
C_{n}
⊙ 1
K
_{1}
,
n
≡ 0(
mod
4) are respectively 3
n
and 3
n
. Let
u
_{1}
,
u
_{2}
,...,
u_{n}
be the cycle vertices of
C_{n}
⊙ 1
K
_{1}
,
v
_{1}
,
v
_{2}
,...,
v_{n}
be the vertices adjacent to
u
_{1}
,
u
_{2}
,...,
u_{n}
and
w
_{1}
,
w
_{2}
,...,
w_{n}
be the vertices adjacent to 1
K
_{1}
,
v
_{1}
,
v
_{2}
,...,
v_{n}
respectively. Obviously
Consider a labeling map
f
:
V
(
G
) → {0, 1,...,3
n
+
k
− 1} defined as follows:
It is clear that
f
is injective and the induced labeling map
f
^{∗}
:
E
(
G
) → {
k, k
+ 1,...,3
n
+
k
− 1} defined as
f
^{∗}
(
u, v
) = |
f
(
u
) −
f
(
v
)| ∀ (
u, v
) ∈
E
(
G
) and
u, v
∈
V
(
G
), where
u
and
v
are adjacent vertices of
G
, is bijective. Thus
f
is
k
-graceful labeling of the graph
G
. For example, the graph obtained by adding pendant edge to each pendant vertex of
C
_{16}
⊙ 1
K
_{1}
and its 3-graceful labeling are shown in
Fig. 2
and
Fig. 3
respectively. □
G′
be a copy of simple graph
G
, let
u_{i}
be the vertices of
G
and
v_{i}
be the vertices of
G′
correspond with
u_{i}
. A new graph denoted by
D
(
G
) is called the double graph of
G
[9]
if
V
(
D
(
G
)) =
V
(
G
) ∪
V
(
G′
) and
E
(
D
(
G
)) =
E
(
G
) ∪
E
(
G′
) ∪{
u_{i}v_{j}
:
u_{i}
∈
V
(
G
),
v_{j}
∈
V
(
G′
) and
u_{i}u_{j}
∈
E
(
G
)}
Theorem 3.1.
Double graph of path P_{n}
(
n
> 1)
is k-graceful
.
Proof
. Let
P_{n}
be a path with
n
vertices
u
_{1}
,
u
_{2}
,...,
u_{n}
and
v_{i}
be the copy of
u_{i}
, then the path
P′_{n}
=
v
_{1}
,
v
_{2}
,...,
v_{n}
be copy of
P_{n}
. Double graph of path
P_{n}
denoted by
D
(
P_{n}
) have order and size 2
n
and 4(
n
−1) respectively. In the following
Fig. 4
,
Fig. 5
and
Fig. 6
, we have shown path
P
_{9}
,
P′
_{9}
and double graph
D
(
P
_{9}
) respectively.
Path P _{9}
Path P′ _{9}
Double graph D (P _{9})
Consider the mapping
f
:
V
(
D
(
P_{n}
)) → {0, 1,...,4(
n
− 1) +
k
− 1} defined as follows:
It is clear that
f
is injective and the induced labeling map
f
^{∗}
:
E
(
D
(
P_{n}
)) → {
k, k
+ 1,...,4(
n
− 1) +
k
− 1} defined as
f
^{∗}
(
u, v
) = |
f
(
u
) −
f
(
v
)| ∀ (
u, v
) ∈
E
(
D
(
P_{n}
)) and
u, v
∈
V
(
D
(
P_{n}
)), where
u
and
v
are adjacent vertices of
D
(
P_{n}
), is bijective. Thus
f
is
k
-graceful labeling of the double graph
D
(
P_{n}
). Hence the double graph
D
(
P_{n}
) is
k
-graceful. In the following
Fig. 7
, we have shown the 3-graceful labeling of the double graph
D
(
P
_{9}
).
3-graceful labeling of the double graph D (P _{9})
□
Theorem 3.2.
Double graph of comb graph P_{n}
⊙ 1
K
_{1}
(
n
> 1)
is k-graceful
.
Proof
. Let {
v
_{1}
,
v
_{2}
,...,
v_{n}
} be the set of path vertices and {
u
_{1}
,
u
_{2}
,...,
u_{n}
} be the set of pendant vertices of comb graph
P_{n}
⊙ 1
K
_{1}
such that
v_{i}
is adjacent to
u_{i}
,
i
= 1, 2,...,
n
. Similarly, let
be the set of path vertices and
be the set of pendant vertices of comb graph (
P_{n}
⊙ 1
K
_{1}
)′ such that
is adjacent to
,
i
= 1, 2,...,
n
. Double graph of comb
P_{n}
⊙1
K
_{1}
denoted by
D
(
P_{n}
⊙ 1
K
_{1}
) have order and size 4
n
and 4(2
n
− 1) respectively. In the following
Fig. 8
, and
Fig. 9
, we have shown comb graph
P
_{7}
⊙ 1
K
_{1}
and double graph
D
(
P
_{7}
⊙ 1
K
_{1}
) respectively.
Comb graph P _{7} ⊙ 1K _{1}
Double graph D (P _{7} ⊙ 1K _{1})
Consider the mapping
f
:
V
(
D
(
P_{n}
)) → {0, 1,...,4(2
n
−1)+
k
−1} defined as follows:
It is clear that
f
is injective and the induced labeling map
f
^{∗}
:
E
(
D
(
P_{n}
⊙ 1
K
_{1}
)) → {
k, k
+1,...,4(2
n
−1)+
k
−1} defined as
f
^{∗}
(
u, v
) = |
f
(
u
)−
f
(
v
)| ∀ (
u, v
) ∈
E
(
D
(
P_{n}
⊙ 1
K
_{1}
)) and
u, v
∈
V
(
D
(
P_{n}
⊙ 1
K
_{1}
)), where
u
and
v
are adjacent ver-tices of
D
(
P_{n}
⊙ 1
K
_{1}
), is bijective. Thus
f
is
k
-graceful labeling of the double graph
D
(
P_{n}
⊙1
K
_{1}
). Hence the double graph
D
(
P_{n}
⊙1
K
_{1}
) is
k
-graceful. In the following
Fig. 10
, we have shown the 4-graceful labeling of the double graph
D
(
P
_{7}
⊙ 1
K
_{1}
).
4-graceful labeling of the double graph D (P _{7} ⊙ 1K _{1})
□
P. Pradhan received M.A. from Banaras Hindu University in 1976 and Ph.D at Patna University in 1987. Since 1997 he has been at Gurukula Kangri University, Haridwar. His research interests in graph theory.
Department of Mathematics and Statistics, Gurukula Kangri University, Haridwar(U.K.)-249404, India.
e-mail: ppradhan14@gmail.com
Kamesh Kumar received M.Sc. from Gurukula Kangri University, Haridwar in 2010 and Pursuing Ph.D. also from Gurukula Kangri University, Haridwar. His research interests in graph labeling and graph theory.
Department of Mathematics and Statistics, Gurukula Kangri University, Haridwar(U.K.)-249404, India
e-mail: kameshkumar.2012@gmail.com

1. Introduction

The
2. Hairy Cycle

A unicycle graph other than a cycle with the property that the removal of any edge from the cycle reduces
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

3. Double graph:

Let
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

BIO

Acharya B.D.
(1984)
Are all polyminoes arbitrarily graceful?, Proc. First Southeast Asian Graph Theory Colloquium (Ed-s: K.M. Koh, H.P. Yap)
Springer-Verlag
N.Y.
205 -
211

Bu C.
,
Zhang D.
,
He B.
(1994)
k-gracefulness of
J. Harbin Shipbuilding Eng. Inst.
15
95 -
99

Deligen
,
Zhao Lingqi
,
Jirimutu
(2012)
On k-gracefulness of r-Crown for complete bipartite graphs
International Journal of Pure and Applied Mathematics
1
17 -
24

Gallian J.A.
(2014)
A dynamic survey of graph labeling
The Electronic Journal of Combinatorics
# DS6
17

Jirimutu
(2003)
On k-gracefulness of r-Crown Ir(K1,n)(n ≥ 2, r ≥ 2) for complete bipartite graphs
Journal of Inner Mongolia University for Nationalities
2
108 -
110

Jirimutu
,
Bao Yu-Lan
,
Kong Fan-Li
(2004)
On k-gracefulness of r-Crown for complete bipar- tite graphs
International Journal of Pure and Applied Mathematics
1
81 -
86

Liang H.X.
,
Liu C.F.
(1991)
On k-gracefulness of graphs
Dongbei Shida Xuebao
33
41 -
44

Liang Zh. H.
,
Sun D.Q.
,
Xu R.J.
(1993)
k-graceful labeling of the wheel graph W2k
J. Hebei Normal College
1
33 -
44

Ma Q.
,
Wang J.
(2011)
The (2, 1)-total labeling of double graph of some graphs
Environmental Sciences
11
281 -
284

Maheo M.
,
Thuillier H.
(1982)
On d-graceful graphs
Ars Combinatoria
13
181 -
192

Pradhan P.
,
Kumar Kamesh
,
Kumar A.
(2013)
Missing numbers in k-graceful graphs
Journal of Computer Applications
79
1 -
6
** DOI : 10.5120/13758-1597**

Seoud M.A.
,
Elsahawi E.A.
(2008)
On variations of graceful labelings
Ars Combinatoria
87
127 -
138

Siqinqimuge
,
Wei Feng
,
Jirimutu
(2011)
k-gracefulness of r-Crown for complete bipartite graphs
International Conference on Information Science and Engineering
1
81 -
86

Slater P.J.
On k-graceful graphs
In: Proc. Of the 13th South Eastern Conference on Combinatorics, Graph Theory and Computing
(1982)
53 -
57

Citing 'ON k-GRACEFUL LABELING OF SOME GRAPHS†
'

@article{ E1MCA9_2016_v34n1_2_9}
,title={ON k-GRACEFUL LABELING OF SOME GRAPHS†}
,volume={1_2}
, url={http://dx.doi.org/10.14317/jami.2016.009}, DOI={10.14317/jami.2016.009}
, number= {1_2}
, journal={Journal of Applied Mathematics & Informatics}
, publisher={Korean Society of Computational and Applied Mathematics}
, author={PRADHAN, P.
and
KUMAR, KAMESH}
, year={2016}
, month={Jan}