 Open Access
 Total Downloads : 1341
 Authors : Veena ShindeDeore, Dr (Mrs.) Manisha M.Acharya
 Paper ID : IJERTV1IS8457
 Volume & Issue : Volume 01, Issue 08 (October 2012)
 Published (First Online): 29102012
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Oddgraceful Labeling of Corona Graph C_{2n}*K _{1}
* Veena ShindeDeore. *Dr (Mrs.) Manisha M.Acharya
Research Scholar, JJT University. Research Guide, JJT University.
Head, Department of Mathematics Associate Professor and Head, Department of And Statistics, Mathematics, Maharshi Dayanand College,
Bhavans H.S. College, Mumbai. Parel, Mumbai.
The research in Graph theory had lead to one of the important area which involves labeling of graphs. There are different types of labelings such as graceful labeling, magic labeling, prime labeling etc applied to various classes of graphs. In this paper, oddgracefulness of the corona graph C2n*K1 for n 2 is obtained.
Keywords:
Graph theory, Graceful graph, labeling of graphs, corona graph, oddgraceful labeling.
Figure 1:Different graphs.
Definition 2: Corona graph: The corona
G1* G2 of two graphs G1 and G2 is a graph G obtained by taking one copy of G1 which has p1vertices and p1copies of G2 and then joining ith vertex of G1 to every vertex in the ith copy of G2.
Definition 1:Graph: A graph G is a pair (V(G) , E (G)) where V (G) is a
C3: K1: o
Figure 2: Corona C3* K1
C3 * K1:
nonempty finite set of elements known as vertices and E (G) is family of unordered pairs of elements of V (G) known as edges.
Definition 3: Difference vertex
labeling: A difference vertex labeling of graph G is an assignment f of labels to
the vertices of G that induces for each edge uv the weight f(u) – f(v)
Figure 3: Difference vertex labeling. Definition 4: Labeled graph: When the dots or lines in a graph are labeled with numbers we call it a labeled graph. Labeling of the vertices of a graph G is assignment of distinct natural numbers to vertices of G. This labeling induces a natural labeling of the edges called edge labels or edge weights.
Figure 4:Labeling of graphs.
Definition 5: Graceful graph: Let G be a graph with q edges. Let f be labeling of G such that the set of labels of vertices is a subset of { 0,1,2,3,……,q} and the set of
the edge labels is from set { 1,2,3,……,q} Then the labeling f is said to be graceful
and graph G is called graceful graph .
Figure 5: Graceful graph.
Definition 6: Oddgraceful graph: A difference vertex labeling of graph G of size n is oddgraceful if f is an injection from V(G) to {0,1,..,2n1} such that the induced weights are {1,3,..,2n1}. The graph with oddgraceful labeling is called oddgraceful graph.
Figure 6: Oddgraceful graph.
Theorem : The graphs C2n*K1 are odd graceful, for n 2.
Proof : Number of vertices of C2n*K1 = p(C2n*K1) = 4n
Number of edges of C2n*K1 = q (C2n*K1)
= 4n
Let vertex set of C2n*K1 be V(C2n*k1) =
{u1,u2, ,u2n ; v1,v2,..,v2n} where vertices u1,u2,..,u2n are vertices of cycle C2n. vi is the pendant vertex adjacent to ui ; 1 i 2n.
There are two cases : (i) n 0 (mod 2)
(ii) n 1 (mod 2)
In both the cases we show that edge weight set is W = {1,3,5,,8n1} with vertex set labeling{0,1,2,3,4,5, ,8n1}.
In both cases, the labeling function f is given in two parts viz Part I and Part II.
Part I describes the labeling function for the vertices (ui,vi) where 1 i n and Part II describes labeling function for the vertices (ui, vi) where n + 1 i 2n. Further in each case, Part II is divided into three subparts namely S1, S2 and S3.
Part I : The labeling function f for vertices ui and vi where 1 i n is given as follows:
f(v2i1) = 4i 4 and f (u2i1) = 8n (4i3) for 1 i when n 0 (mod 2)
and
for 1 i + 1 when n 1(mod 2)
f (v2i) = 8n (4i1) and f ( u2i) = 4i 2 for 1 i when n 0 (mod 2)
and
for 1 i when n 1 (mod 2)
The edge weights covered in Part I are all odd numbers in descending order from 8n 1 to 4n + 3 i.e. from 8n 1 to 8n (4n – 3).
Part II : As mentioned earlier, Part II is divided into three subparts S1, S2 and S3.
Subpart S1 : In this subpart we have to consider only two vertices un+1 and
vn+1. The labeling function for this subpart is as follows:
f (un+1) = 2n 1 and f (vn +1) = 6n 2 when n 0 (mod 2)
f (un +1) = 6n 2 and f (vn+1) = 2n 1 when n 1 (mod 2)
Subpart S2 : The labeling function f in this subpart is defined for vertices un+2, un+3, , u2n1 and for vertices vn+2, vn+3,…,v2n1.
f(u2i) = 4i 2 and f(v2i) = 8n (4i 1) for +1 i n 1
when n 0 (mod 2) and
for +2 i n1 when n 1(mod 2)
f(u2i + 1) = 8n (4i +1) and f(v2i+1) = 4i for + 1 i n 1
when n 0 (mod 2)
and
for + 1 i n 1 when n 1 (mod 2)
Remark :i) When n 0 (mod 2), in subpart S2, for the validity of the range of the parameter i, we need n 4. For

n <4, we have only one such value of n which is 2. When n =2, the set of vertices belonging to S2 is an empty set.
ii) When n 1 (mod 2), in subpart S2, for the validity of the range of the parameter i , we need n 3. For

n < 5 we have only one value of n which is 3. When n = 3 the set of vertices belonging to S2 are u5 and v5.
Subpart S3 : In this subpart there are only two vertices viz ; u2n and v2n with labeling function as follows:
f (u2n) = 4n 2 and f(v2n) = 1
if n 0 (mod 2) and n 1 (mod 2)
All odd edge weights in descending order from 8n1 to 4n + 3 are covered in Part I. Remaining odd edge weights from 4n +1 to 1 are covered in Part II as follows :
1. f(u1) f(u2n) = 4n + 1
2. f(vn+1) f(un+1) = 4n – 1
3. f(u2n) f(v2n) = 4n – 3
4. For +1 i n1 edge weights covered are from 4n 5 to 7 in descending order.
5. f (u2n1) f (u2n) = 5
6. f (un +2) f (un+1) = 3.
7. f (un+1) f (un) = l
Remark : i)In case of n 0 (mod 2), when n = 2, edge weights covered in PartI are from 8n1 to 4n +3 .i.e. 15, 13 and 11, then in subpart S1 edge weights covered are 1 and 7. Since subpart S2 is empty for n = 2, we get
f (u2n) f(un+1) = 4n 2 (2n1) = 2n1 = 3.
Thus, edge weights covered in subpart S3 are 5 & 9.
ii) In case of n 1 (mod 2), when n =3, the edge weights covered in Part I are from 8n1 to 4n +3 .i.e. 23,21,19,17,15. In subpart S1 edge weights covered are 3 & 11. In subpart S2, edge weights covered are 1,7 and 5. In subpart S3, edge weights covered are 9 and 13.
Thus, the labeling function f is injective and that each odd edge weight from 1 to 8n1 is covered exactly once. Hence, the graph C2n*K1 is oddgraceful for n 2.
Illustration1:
Figure 7: Oddgracefulness of C8*K1
Illustration 2:
Figure 8: Oddgracefulness of C10*K1
The odd graceful labeling is presented to the corona graph C2n*K1.The corona graph C2n*K1 is thus a edgeodd graceful graph. It is interesting to apply this
labeling to certain classes of graph. It is also area of interest to make computer programmes for the given labeling.

A.Rosa(1966), On certain valuations of the vertices of a graph; Theory of Graphs (International symposium, Rome, Gordon and Breach,
N.Y. and Dunod Paris),pp. 349355.

Christian Barrientos(2009), Odd graceful labeling of trees of diameter 5,AKCE J. Graphs.Combin.,Vol 6,No.2,pp. 17.

Christian Barrientos(2002), Graceful labeling of Chains and Corona graphs, Bull. Inst.Combin.AppliVol34,pp. 1726.

Timothy A. Redl(2003), Graceful Graphs and Graceful labeling: Two mathematical programming formulations and some other new results; Computational and Applied mathematics; pp. 113.

Christian Barrientos(2005), Graceful graphs with pendant edges; Australian journal of Combinatorics, Vol 33,pg:99107.

Christian Barrientos(2002), Equitable labeling of Corona graphs, JCMCC,Vol 41,pp. 139149.

J.Suresh Kumar(1997), The corona of an odd cycle on a star is sequential and harmonics, Indian J. of
pure appl. Math.,Vol28,No.8 , pp. 1005 1007.

J.A.Gallian(2011), A dynamic survey of graph labeling, Electronic Journal of Combinatorics,DS6.

A. Solairaju and K. Chitra(2009), Edge odd graceful labeling of some graphs, Electronic notes in Discrete Mathematics, Vol 33, pp. 1518.

F.Harary(1972), Graph Theory, AddisonWesley Publishing Company,pp. 167
***************