Advanced
ON k-GRACEFUL LABELING OF SOME GRAPHS†
ON k-GRACEFUL LABELING OF SOME GRAPHS†
Journal of Applied Mathematics & Informatics. 2016. Jan, 34(1_2): 9-17
Copyright © 2016, Korean Society of Computational and Applied Mathematics
  • Received : June 15, 2015
  • Accepted : July 25, 2015
  • Published : January 30, 2016
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
About the Authors
P. PRADHAN
KAMESH KUMAR

Abstract
In this paper, it has been shown that the hairy cycle Cn rK 1 , n ≡ 3( mod 4), the graph obtained by adding pendant edge to each pendant vertex of hairy cycle Cn ⊙ 1 K 1 , n ≡ 0( mod 4), double graph of path Pn and double graph of comb Pn ⊙ 1 K 1 are k -graceful. AMS Mathematics Subject Classification : 05C78.
Keywords
1. Introduction
The 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 Cn 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 Cn , 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 Km,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 Cn rK 1 , n ≡ 3( mod 4) is k -graceful and the graph obtained by adding pendant edge to pendant vertex of hairy cycle Cn ⊙ 1 K 1 , n ≡ 0( mod 4) is also k -graceful.
2. Hairy Cycle
A unicycle graph other than a cycle with the property that the removal of any edge from the cycle reduces G to a caterpillar is called hairy cycle. The corona of cycle Cn and rK 1 i.e. Cn rK 1 is the example of hairy cycle.
Theorem 2.1. The hairy cycle Cn rK 1 , n ≡ 3( mod 4) is admits k-graceful labeling where k r .
Proof . Let ui ( i = 1, 2,..., n ) be the cycle vertices of hairy cycle Cn rK 1 and the vertices of the r -hanged edges connected to each ui ( i = 1, 2,..., n ) are denoted by uit ( t = 1, 2,..., r ).
Consider the map f : V ( Cn rK 1 ) → {0, 1,..., n ( r +1)+ k −1} defined as follows:
PPT Slide
Lager Image
and
PPT Slide
Lager Image
It is easy to check that f is injective mapping from V ( Cn rK 1 ) to {0, 1,..., n ( r +1) + k − 1}. Now we prove that the induced mapping f : E ( Cn 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 ( Cn rK 1 ). Let
PPT Slide
Lager Image
The edge label induced by f is as follows.
PPT Slide
Lager Image
We tide up the elements of each set and have a union
PPT Slide
Lager Image
So the induced mapping f is a bijective mapping from V ( Cn rK 1 ) onto { k, k + 1,..., n ( r + 1) + k − 1}. Thus, the hairy cycle Cn 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 . □
PPT Slide
Lager Image
3-graceful labeling of hairy cycle C7 ⊙ 4K1
Theorem 2.2. The graph obtained by adding pendant edge to each pendant vertex of hairy cycle Cn ⊙ 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 Cn ⊙ 1 K 1 , n ≡ 0( mod 4) are respectively 3 n and 3 n . Let u 1 , u 2 ,..., un be the cycle vertices of Cn ⊙ 1 K 1 , v 1 , v 2 ,..., vn be the vertices adjacent to u 1 , u 2 ,..., un and w 1 , w 2 ,..., wn be the vertices adjacent to 1 K 1 , v 1 , v 2 ,..., vn respectively. Obviously
PPT Slide
Lager Image
Consider a labeling map f : V ( G ) → {0, 1,...,3 n + k − 1} defined as follows:
PPT Slide
Lager Image
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. □
PPT Slide
Lager Image
PPT Slide
Lager Image
3. Double graph:
Let G′ be a copy of simple graph G , let ui be the vertices of G and vi be the vertices of G′ correspond with ui . 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′ ) ∪{ uivj : ui V ( G ), vj V ( G′ ) and uiuj E ( G )}
Theorem 3.1. Double graph of path Pn ( n > 1) is k-graceful .
Proof . Let Pn be a path with n vertices u 1 , u 2 ,..., un and vi be the copy of ui , then the path P′n = v 1 , v 2 ,..., vn be copy of Pn . Double graph of path Pn denoted by D ( Pn ) 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.
PPT Slide
Lager Image
Path P9
PPT Slide
Lager Image
Path P′9
PPT Slide
Lager Image
Double graph D(P9)
Consider the mapping f : V ( D ( Pn )) → {0, 1,...,4( n − 1) + k − 1} defined as follows:
PPT Slide
Lager Image
It is clear that f is injective and the induced labeling map f : E ( D ( Pn )) → { k, k + 1,...,4( n − 1) + k − 1} defined as f ( u, v ) = | f ( u ) − f ( v )| ∀ ( u, v ) ∈ E ( D ( Pn )) and u, v V ( D ( Pn )), where u and v are adjacent vertices of D ( Pn ), is bijective. Thus f is k -graceful labeling of the double graph D ( Pn ). Hence the double graph D ( Pn ) is k -graceful. In the following Fig. 7 , we have shown the 3-graceful labeling of the double graph D ( P 9 ).
PPT Slide
Lager Image
3-graceful labeling of the double graph D(P9)
Theorem 3.2. Double graph of comb graph Pn ⊙ 1 K 1 ( n > 1) is k-graceful .
Proof . Let { v 1 , v 2 ,..., vn } be the set of path vertices and { u 1 , u 2 ,..., un } be the set of pendant vertices of comb graph Pn ⊙ 1 K 1 such that vi is adjacent to ui , i = 1, 2,..., n . Similarly, let
PPT Slide
Lager Image
be the set of path vertices and
PPT Slide
Lager Image
be the set of pendant vertices of comb graph ( Pn ⊙ 1 K 1 )′ such that
PPT Slide
Lager Image
is adjacent to
PPT Slide
Lager Image
, i = 1, 2,..., n . Double graph of comb Pn ⊙1 K 1 denoted by D ( Pn ⊙ 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.
PPT Slide
Lager Image
Comb graph P7 ⊙ 1K1
PPT Slide
Lager Image
Double graph D(P7 ⊙ 1K1)
Consider the mapping f : V ( D ( Pn )) → {0, 1,...,4(2 n −1)+ k −1} defined as follows:
PPT Slide
Lager Image
It is clear that f is injective and the induced labeling map f : E ( D ( Pn ⊙ 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 ( Pn ⊙ 1 K 1 )) and u, v V ( D ( Pn ⊙ 1 K 1 )), where u and v are adjacent ver-tices of D ( Pn ⊙ 1 K 1 ), is bijective. Thus f is k -graceful labeling of the double graph D ( Pn ⊙1 K 1 ). Hence the double graph D ( Pn ⊙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 ).
PPT Slide
Lager Image
4-graceful labeling of the double graph D(P7 ⊙ 1K1)
BIO
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
References
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