International Journal of Scientific & Engineering Research Volume 4, Issue 1, January-2013 1

ISSN 2229-5518

.

A NEW CLASS OF GRACEFULL TREES

A. SOLAIRAJU¹ and N. ABDUL ALI²

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

1email: solairama@yahoo.co.in; 2 email: abdul_ali_2003@yahoo.com

Abstract : The gracefulness of Tp-tree of size (5n, 5n-1) is obtained

Introduction:

Most graph labeling methods trace their origin to one introduced by Rosa [2] or one given Graham and Sloane [1]. Rosa de- fined a function f, a P-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 as- signed the label If(x)-f(y)I, 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,8,9]
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 ob- tained (3) edge-odd Gracefulness of a span- ning 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
(i) f is one – to – one
(ii) The edges receive all the la- bels (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.

International Journal of Scientific & Engineering Research Volume 4, Issue 1, January-2013 2

ISSN 2229-5518

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

Example 1.1: The circuit C4 is a graceful graph as follows:

Section – II: Tp–(5n, 5n-1) tree

Definition 2.1: n L1 P5 is a tree, becoming a path by moving edges between vertices of degree 3 defined in the following manner only. That is, it is a Tp-tree obtained from n copies of P5, and connected acyclic in the fol- lowing manner.

International Journal of Scientific & Engineering Research Volume 4, Issue 1, January-2013 3

ISSN 2229-5518

Proof: Due to definition (2.1), Tp–(5n,5n-1) is a connected graph (see figures 1 and 2) according as n is odd or even.

Figure 1 ( n is odd)
Figure 2 ( n is even)

Case (1): n is odd.

The labelings of vertices and edges for Tp–
Figure 2 ( n is even)

Main theorem 2.2: The connected graph

Tp–tree with p=5n and q=5n-1 is graceful.
(5n,5n-1) (Figure 1) are as follows:

Define f: v(G) -7 {0,1,2,…q)

International Journal of Scientific & Engineering Research Volume 4, Issue 1, January-2013 4

ISSN 2229-5518

By

Define f+:E(G)-7 {1,2,3..q} by f+ (u,v)=
|f(u)-(v)|, u,v € E(G).
Hence, the bisection maps f for vertices and f+ for edges in Tp–(5n,5n-1) satisfies all
condition of graceful labeling. Thus, Tp–
(5n,5n-1) is a graceful if n is odd.

Case (2): n is even.

The labeling of vertices and edges for Tp– (5n,5n-1) (Figure 2) are as follows:
Define f: v(G) -7 {0,1,2,…q) By

International Journal of Scientific & Engineering Research Volume 4, Issue 1, January-2013 5

ISSN 2229-5518

Define f+: E(G)-7 {1,2,3..q} by f+ (u,v)=
|f(u)-(v)|, u,v € E(G).
Hence, the bisection maps f for vertices and f+ for edges in Tp–(5n,5n-1) satisfies all the conditions of graceful labeling. Thus, Tp– (5n,5n-1) is a graceful if n is even.

Corollary 2.3: Tp–(5n,5n-1) is a graceful

tree

Example 2.1 :

The graph 5 L1 P5 is a graceful graph.

Example 2.2:

The graph 6 L1 P5 is a graceful graph.

References:

1. R. L. Graham and N. J. A. Sloane, On additive bases and harmonious graph, SIAM J. Alg. Dis- crete 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.

International Journal of Scientific & Engineering Research Volume 4, Issue 1, January-2013 6

ISSN 2229-5518

4. A. Solairaju and P.Muruganantham, even-edge gracefulness of ladder, The Global Journal of Ap- plied 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 publi- cation 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, A.Sasikala, C.Vimala, Edge-odd Gracefulness of a spanning tree of Cartesian product of

P2 and Cn, The Global Journal of Pure and Applied Mathematics of Mathematical Sciences, (Preprint).

8. A. Solairaju, C.Vimala,A.Sasikala Gracefulness of a spanning tree of the graph of Carte-

sian product of Sm and Sn, The Global Journal of Pure and Applied Mathematics of Ma- thematical Sciences, Vol. 1, No-2 (July-Dec 2008): pp117-120.

9. A.Solairaju, C.Vimala, A.Sasikala , Even Edge Gracefulness of the Graphs, The

Global Journal of Pure and Applied Mathematics of Mathematical Sciences, (Preprint).