Gracefull Ness of P_k∘ 2_Ck

Gracefull Ness of P_k 2_Ck

Gracefull Ness Of Pk 2

A. Solairaju¹ And N. Abdul Ali²

1-2: P.G. & Research Department of Mathematics, Jamal Mohamed College, Trichy 20.

Abstract: In this paper, we obtained that the connected graph Pk 2C4 is graceful.

Most graph labeling methods trace their origin to one introduced by Rosa [2] or one given Graham and Sloane [1]. Rosa defined a function f, a -valuation of a graph with q edges if f is an injective map from the vertices of G to the set {0, 1, 2 ,,q} such that when each edge xy is assigned the label f(x)-f(y), the resulting edge labels are distinct.

A. Solairaju and K. Chitra [3] first introduced the concept of edge-odd graceful labeling of graphs, and edge-odd graceful graphs.

A. Solairaju and others [5,6,7] proved the results that(1) the Gracefulness of a spanning tree of the graph of Cartesian product of Pm and Cn,was obtained (2) the Gracefulness of a spanning tree of the graph of cartesian product of Sm and Sn, was obtained (3) edge-odd Gracefulness of a spanning tree of Cartesian product of P2 and Cn was obtained (4) Even -edge Gracefulness of the Graphs was obtained (5) ladder P2 x Pn is even-edge graceful, and (6) the even-edge gracefulness of Pn O nC5 is obtained.

Section I : Preliminaries

Definition 1.1: Let G = (V,E) be a simple graph with p vertices and q edges.

A map f :V(G) {0,1,2,,q} is called a graceful labeling if

1. f is one to one

2. The edges receive all the labels (numbers) from 1 to q where the label of an edge is the absolute value of the difference between the vertex labels at its ends.

A graph having a graceful labeling is called a graceful graph.

Example 1.1: The graph 6 P5 is a graceful graph.

Section II Path merging with circulits of length four

Definition 2.1: Pk 2C4 is a connected graph obtained by merging a circuit of length 4 with isolated vertex of a path of length k.

Theorem 2.1: The connected graph Pk 2C4 is graceful.

T2

VK+2

T1 T2

V1 V2 V3 V4 V5 V6 VK-1 VK

VK+1

VK+4

T3 VK+3

Define f: V {1,, q} by

f(T1) = 0; f(T2) = q, f(T3) = q-1, f(T4) = 2

f(V ) = (q-2) (1), i is odd, i =1,3, , k+1

i 2

(2+ ), i is even, i = 2,4,, k+2

2

f(Vk+3) = f(Vk+2) + 1 f(Vk+4) = f(Vk+3) + 1

T2

VK+2

T1 T2

VK+1

VK+4

V1 V2 V3 V4 V5 V6

VK-2

VK-1 VK

T3 VK+3

Define f: V {1,, q}by

f(T1) = 0; f(T2) = q, f(T3) = q-1, f(T4) = 2

f(V ) = (q-2) (1), i is odd, i =1,3, , k, k+2

i 2

(2+ ), i is even, i = 2,4,, k+1

2

f(Vk+3) = f(Vk+2) – 1 f(Vk+4) = f(Vk+3) – 1

Example 2.1: k = 11 (odd) ; P: V | 19; Q: e | 20

12

20

18

20

16 15 14 13 12 11

0 2

10 09 08

07 06

04 02

05

8 10

19 17

18 3

17 4 16 5 15 6 14 7 13

03 01

19 11

Example 2.2: k =14 (even) ; P: V | 22; Q: e | 23

23

21

23

19 18 17 16 15 14

13 12 11

10 09 08

10

04 02

07 06 05

0 2

22 20

21 3

20 4 19 5 18 6 17 7 16

8 15 9

14 12

03 01

22 11

References:

1. R. L. Graham and N. J. A. Sloane, On additive bases and harmonious graph, SIAM J. Alg. Discrete Math., 1 (1980) 382 404.

2. A. Rosa, On certain valuation of the vertices of a graph, Theory of graphs (International Synposium,Rome,July 1966),Gordon and Breach, N.Y.and Dunod Paris (1967), 349-355.

3. A.Solairaju and K.Chitra Edge-odd graceful labeling of some graphs, Electronics Notes in

   Discrete Mathematics Volume 33,April 2009,Pages 1.

4. A. Solairaju and P.Muruganantham, even-edge gracefulness of ladder, The Global Journal of Applied Mathematics & Mathematical Sciences(GJ-AMMS). Vol.1.No.2, (July-December- 2008):pp.149-153.

5. A. Solairaju and P.Sarangapani, even-edge gracefulness of Pn O nC5, Preprint (Accepted for publication in Serials Publishers, New Delhi).

6. A.Solairaju, A.Sasikala, C.Vimala Gracefulness of a spanning tree of the graph of product of Pm and Cn, The Global Journal of Pure and Applied Mathematics of Mathematical Sciences, Vol. 1, No-2 (July-Dec 2008): pp 133-136.

7. A. Solairaju, C.Vimala,A.Sasikala Gracefulness of a spanning tree of the graph of Cartesian product of Sm and Sn, The Global Journal of Pure and Applied Mathematics of Mathematical Sciences, Vol. 1, No-2 (July-Dec 2008): pp117-120.