Odd-graceful Labeling of Corona Graph C_2n*K ₁

Odd-graceful Labeling of Corona Graph C_2n*K ₁

* Veena Shinde-Deore. *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, odd-gracefulness of the corona graph C2n*K1 for n 2 is obtained.

Keywords:

Graph theory, Graceful graph, labeling of graphs, corona graph, odd-graceful 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 p1-vertices and p1-copies 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: Odd-graceful graph: A difference vertex labeling of graph G of size n is odd-graceful if f is an injection from V(G) to {0,1,..,2n-1} such that the induced weights are {1,3,..,2n-1}. The graph with odd-graceful labeling is called odd-graceful graph.

Figure 6: Odd-graceful 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,,8n-1} with vertex set labeling{0,1,2,3,4,5, ,8n-1}.

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 S-1, S-2 and S-3.

Part -I : The labeling function f for vertices ui and vi where 1 i n is given as follows:

f(v2i-1) = 4i -4 and f (u2i-1) = 8n (4i-3) for 1 i when n 0 (mod 2)

and

for 1 i + 1 when n 1(mod 2)

f (v2i) = 8n (4i-1) 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 S-1, S-2 and S-3.

Subpart S-1 : 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 S-2 : The labeling function f in this subpart is defined for vertices un+2, un+3, , u2n-1 and for vertices vn+2, vn+3,…,v2n-1.

f(u2i) = 4i -2 and f(v2i) = 8n (4i -1) for +1 i n 1

when n 0 (mod 2) and

for +2 i n-1 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 S-2, for the validity of the range of the parameter i, we need n 4. For

1. n <4, we have only one such value of n which is 2. When n =2, the set of vertices belonging to S-2 is an empty set.

   ii) When n 1 (mod 2), in subpart S-2, for the validity of the range of the parameter i , we need n 3. For

2. n < 5 we have only one value of n which is 3. When n = 3 the set of vertices belonging to S-2 are u5 and v5.

Subpart S-3 : 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 8n-1 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 n-1 edge weights covered are from 4n 5 to 7 in descending order.

5. f (u2n-1) 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 Part-I are from 8n-1 to 4n +3 .i.e. 15, 13 and 11, then in subpart S-1 edge weights covered are 1 and 7. Since subpart S-2 is empty for n = 2, we get

f (u2n) f(un+1) = 4n 2 (2n-1) = 2n-1 = 3.

Thus, edge weights covered in subpart S-3 are 5 & 9.

ii) In case of n 1 (mod 2), when n =3, the edge weights covered in Part -I are from 8n-1 to 4n +3 .i.e. 23,21,19,17,15. In subpart S-1 edge weights covered are 3 & 11. In subpart S-2, edge weights covered are 1,7 and 5. In subpart S-3, edge weights covered are 9 and 13.

Thus, the labeling function f is injective and that each odd edge weight from 1 to 8n-1 is covered exactly once. Hence, the graph C2n*K1 is odd-graceful for n 2.

Illustration1:

Figure 7: Odd-gracefulness of C8*K1

Illustration 2:

Figure 8: Odd-gracefulness of C10*K1

The odd graceful labeling is presented to the corona graph C2n*K1.The corona graph C2n*K1 is thus a edge-odd 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.

1. 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. 349-355.

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

3. Christian Barrientos(2002), Graceful labeling of Chains and Corona graphs, Bull. Inst.Combin.AppliVol-34,pp. 17-26.

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

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

6. Christian Barrientos(2002), Equitable labeling of Corona graphs, JCMCC,Vol- 41,pp. 139-149.

7. J.Suresh Kumar(1997), The corona of an odd cycle on a star is sequential and harmonics, Indian J. of

   pure appl. Math.,Vol-28,No.8 , pp. 1005- 1007.

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

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

10. F.Harary(1972), Graph Theory, Addison-Wesley Publishing Company,pp. 167

***************