Printer Friendly

Gracefulness of a new class from copies of [E.sub.n]-tree and n[nabla][C.sub.3].

Introduction

When studying graceful labeling, only simple graph is considered. A graceful labeling of an undirected graph G with q edges is a one-to-one function from the set of vertices of G to the set {0, 1, 2,...,q}such that the induced edge labels are all distinct. An induced edge label is the absolute value of the difference between the two end vertex labels.

A complete and current summary of graceful and non-graceful results along with some unproven conjectures can be found in Gallian's dynamic survey [1] of graceful labeling.

Solairaju and Ambika [2] have proved that the n copies of cycles C4 is graceful.

Solairaju and Ambika [3] have showed that the connected graph [E.sub.k] * [S.sub.n+i] (copies of k number of stars) is a graceful graph. Also they [4] obtained a result that n[C.sub.3] (n number of [C.sub.3]) and its mirror image are graceful. Similarly they got double n[C.sub.3] is graceful.

Solairaju and Ambika [5] have showed that a unicycle graph from Copies of Stars on cycles is a graceful graph.

Known Results

Definition 2.1

The graceful labeling of a graph G with q edges is a function f : V(G) [right arrow] {0,1,2,...,q} such that distinct vertices receive distinct numbers and {[absolute value of f(u)-f(v)]: uv [member of] E(G)}={1,2,3,...,q}. A graph is graceful if it has a graceful labeling.

Definition 2.2

A cycle C in a graph is a connected subgraph in which the degree of every vertex in C is two. A cycle with n vertices is denoted by [C.sub.n].

Definition 2.3

The graph n[nabla][C.sub.3] (Copies of [C.sub.3] with one edge common) is a connected graph, which has{[V.sub.0],[V.sub.1],[V.sub.2],...,[v.sub.n+1]}as a vertex set. [v.sub.0] and [v.sub.1] is adjacent to all the remaining vertices and [v.sub.0][v.sub.1] is common to all the copies of [C.sub.3]. Also [v.sub.i] adjacent to [v.sub.i+1], for i = 2,3,4,...,n+1. The graph n[nabla][C.sub.3] is shown in the following figure 1

[FIGURE 1 OMITTED]

Definition 2.4

An [E.sub.n]-Tree is a tree, which has {[v.sub.0],[v.sub.1],[v.sub.2],...,[v.sub.6n-1]}as a vertex set and it is as follows.

[ILLUSTRATION OMITTED]

The arbitrary labeling of [E.sub.n]-Tree is mentioned in figure 2.

[FIGURE 2 OMITTED]

Gracefulness of n[nabla][C.sub.3] and Copies of [E.sub.n]-Tree

Theorem 3.1

The connected graph n[nabla][C.sub.3] is graceful.

Proof: The graph n[nabla][C.sub.3] is a connected graph followed from definition 2.3 The graph n[nabla][C.sub.3] has (n+1) vertices and 3n edges. The graph n[nabla][C.sub.3] has an arbitrary labeling of vertices as in figure 1.

To be graceful of above graph, define a map f: V [right arrow] {0,1,2,...,3n} by f([v.sub.0]) = 0 ; f([v.sub.1]) = n ; f([v.sub.2i]) = 3n-(i-1) and f(v2i+1) = 2n+ i for i=1,2,3,...

By usual way to label the edges of n[nabla][C.sub.3], e(uv) = [absolute value off(u)-f(v)] is edge labeling of the graph.

Now f and e are both satisfy all conditions of graceful labeling. Hence n[nabla][C.sub.3] is graceful.

Example 3.1: The connected graph 3[nabla][C.sub.3] is graceful.

Gracefulness of the graph, Copies of 3[C.sub.3] with 9 edges such that the vertex set V={[v.sub.0], [v.sub.1], [v.sub.2], [v.sub.3], [v.sub.4]} is labeled in the following manner which is shown in figure 3 The vertex labels are calculated as follows

When n = 3, [v.sub.0] = 0 ; [v.sub.1] = 3 ; For i =1, [v.sub.2] = 9 ; [v.sub.3] = 7; For i = 2, [v.sub.4] = 8

[FIGURE 3 OMITTED]

Theorem 3.2

The graph [E.sub.n]-Tree is graceful when n is odd

Proof: An [E.sub.n]-Tree is a connected simple graph, which has {[v.sub.0], [V.sub.1], [v.sub.2],...,[v.sub.6n-1]}as a vertex set. The graph [E.sub.n] is a copy of E and image of E are drawn simultaneously with lower ends is connected together. The graph En is (6n, 6n-1) graph and vertex labeling are given in figure 4.

Define f : V(G) [right arrow] { 0,1,2,...,6n-1} by f([v.sub.i]) = i ,where i = 0,1,2,...,6n-1, and n is odd.

By usual way to label the edges of [E.sub.n]-tree, e(uv) = [absolute value of f(u)-f(v)] is edge labeling of the graph. Now f and e are both satisfy all conditions of graceful labeling. All the vertices are labeled in left topmost vertex starting from [v.sub.6n-1], ended with [v.sub.3n-3] and adjacent of [v.sub.6n-1] is [v.sub.0]. Also leftmost bottom vertex starting from [v.sub.6n- 3] and ended with [v.sub.3n-1]

[FIGURE 4 OMITTED]

Example 3.2

The graph [E.sub.3]-Tree is graceful.

Based on Theorem 3.2, when n = 3, the gracefulness of graph [E.sub.3] with 18 vertices and 17 edges, is labeled in the following manner which is shown in figure 5.

[FIGURE 5 OMITTED]

Theorem 3.3

The graph [E.sub.n] is graceful when n is even

Proof: An [E.sub.n]-Tree is a connected simple graph, which has {[v.sub.0], [V.sub.1], [v.sub.2],...,[v.sub.6n-1]}as a vertex set. The graph [E.sub.n] is a copy of E and image of E are drawn simultaneously with lower ends is connected together. The graph [E.sub.n] is (6n, 6n-1) graph and vertex labeling are given in figure 2.

Define f : V(G) [right arrow] { 0,1,2,...,6n-1} by f(v) = i ,where i = 0,1,2,...,6n-1, and n is even.

By usual way to label the edges of [E.sub.n]-tree, e(uv) = [absolute value of f(u)-f(v)] is edge labeling of the graph. Now f and e are both satisfy all conditions of graceful labeling. All the vertices are labeled in left topmost vertex starting from [v.sub.6n-1], ended with [v.sub.3n-1] and adjacent of [v.sub.6n-1] is [v.sub.0]. Also leftmost bottom vertex starting from [v.sub.6n- 3] and ended with [v.sub.3n-3].

Example 3.3

The graph E4 -Tree is graceful.

Based on Theorem 3.2, when n = 4, the gracefulness of graph [E.sub.4] with 24 vertices and 23 edges, is labeled in the following manner which is shown in figure 6.

[FIGURE 6 OMITTED]

References

[1] J. A. Gallian. A Dynamic Survey of Graph Labeling. The Electronic Journal of Combinatorics,(DS6), 2009. 12th edition.

[2] A. Solairaju and S. Ambika, A new class of graceful graphs, Antarctica. J. Math., 5(2)(2008), 65-76

[3] A. Solairaju and S. Ambika, Gracefulness of a new class from copies of stars, communicated to International Journal of computer application USA.

[4] A. Solairaju and S. Ambika, Gracefulness of a new class of mirror image of copies of n[C.sub.3] and mirror image of copies of double nC3, communicated to Far East Journal of applied Mathematics in Pushpa publishing house.

[5] A. Solairaju and S. Ambika, Gracefulness of a unicycle graph from Copies of Stars on Cycles, communicated to Electronic Notes in discrete Mathematics in Elsevier Publication.

(1) A. Solairaju and (2) S. Ambika

(1) Associate Professor of Mathematics, Jamal Mohamed College, Trichy-20, India

E-mail: solairama@yahoo.co.in

(2) Assistant Professor of Mathematics, Government Arts College, Coimbatore-18, India

E-mail: ambisadha@yahoo.com
COPYRIGHT 2012 Research India Publications
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2012 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Solairaju, A.; Ambika, S.
Publication:International Journal of Computational and Applied Mathematics
Date:Mar 1, 2012
Words:1350
Previous Article:A class of limit theorems for arbitrary information source on generalized random selection systems.
Next Article:Gracefulness of a new class from copies of [P.sub.n.sup.*] k[C.sub.4] and [P.sub.n.sup.*] k[C.sub.4].

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |