American Journal of Applied Mathematics
Volume 3, Issue 3-1, June 2015, Pages: 14-18

Odd Graceful Labeling of Acyclic Graphs

Ayesha Riasat1, Sana Javed2

1Mathematics Department, University of Management and Technology, Lahore, Pakistan

2Mathematics Department, Comsats Institute of information Technology, Lahore, Pakistan

(A. Riasat)
(S. Javed)

Ayesha Riasat, Sana Javed. Odd Graceful Labeling of Acyclic Graphs. American Journal of Applied Mathematics. Special Issue: Proceedings of the 1st UMT National Conference on Pure and Applied Mathematics (1st UNCPAM 2015). Vol. 3, No. 3-1, 2015, pp. 14-18. doi: 10.11648/j.ajam.s.2015030301.13

Abstract: Let G = (V, E) be a finite, simple and undirected graph. A graph G with q edges is said to be odd-graceful if there is an injection f : V (G) ® {0, 1, 2, . . . , 2q- 1} such that, when each edge xy is assigned the label |f (x)- f (y)| , the resulting edge labels are {1, 3, 5, . . . , 2q- 1} and f is called an odd graceful labeling of G. Motivated by the work of Z. Gao [6] in which he studied the odd graceful labeling of union of any number of paths and union of any number of stars, we have determined odd graceful labeling for some other union of graphs. In this paper we formulate odd-graceful labeling for disjoint unions of graphs consisting of generalized combs, stars, bistars and paths.

1. Introduction

Most graph labeling methods trace their origin to one introduced by Rosa [12] in 1967, or one given by Graham and Sloane [9] in 1980. Rosa [12] called a function  a -valuation of a graph  with  edges if  is an injection from the vertices of  to the set  such that, when each edge  is assigned the label, the resulting edge labels are distinct. Golomb [8] subsequently called such labeling graceful and this is now the popular term. Rosa introduced -valuations as well as a number of other labeling as tools for decomposing the complete graph into isomorphic subgraphs. In particular, -valuations originated as a mean of attacking the conjecture of Ringel [11] that  can be decomposed into  subgraphs that are all isomorphic to a given tree with  edges.

When a graceful labeling  of a graph  has the property that there exists an integer  such that for each edge  of  either  or ,  is named an -labeling and  is said to be an -graph. From the definition it is possible to deduce that a -graph is necessarily bipartite and that the number  (called the boundary value of) is the smaller of the two vertex labels that yield the edge with weight. Some examples of -graphs are the cycle when, the complete bipartite graph, and caterpillars (i.e., any tree with the property that the removal of its end vertices leaves a path). For detailed studies one can see [2] and [1].

A little less restrictive than -labeling are the odd-graceful labeling introduced by Gnanajothi in 1991 [7]. A graph  of size  is odd-graceful if there is an injection  such that the set of induced weights is. In this case,  is said to be an odd-graceful labeling of. One of the applications of this labeling is that trees of size, with a suitable odd-graceful labeling, can be used to generate cyclic decompositions of the complete bipartite graph.

In general graph labeling serves as useful model for a broad range of applications such as: radar, communications network, circuit design, coding theory, astronomy, x-ray, crystallography, data base management and models for constraint programming over finite domains.

Gnanajothi proved that the class of odd-graceful graphs lies between the class of graphs with -labeling and the class of bipartite graphs by showing that every graph with an -labeling has an odd-graceful labeling and every graph with an odd cycle is not odd-graceful. She also proved the following graphs are odd-graceful:,  if and only if  is even,  and combs.

She conjectured that all trees are odd-graceful and proved the conjecture for all trees with order up to . Barrientos [3] has extended this to trees of order up to. Eldergill [4] generalized Gnanajothi’s result on stars by showing that the graphs obtained by joining one end point from each of any odd number of paths of equal length are odd-graceful.

A detailed account of results in the subject of graph labelings can be found in Gallian’ survey [5].

Gao [6] has proved the following graphs are odd-graceful: the union of any number of paths; the union of any number of stars; the union of any number of stars and paths; ; ; and the union of any number of cycles each of which has order divisible by .

In [10] authors have found odd graceful labeling of  and  for  and . Further odd graceful labeling of two copies of generalized combs are discussed along with their disjoint union with other well known families of graphs, also an open problem was proposed to find the odd graceful labeling of union of  with for. Motivated by this open problem in [10], in this paper we have defined odd graceful labeling for  union for. We also formulate an odd graceful labeling of the union of,  with paths and stars.

1.1. Definition 1

A generalized comb is a graph derived from the path,  by adding  new paths  of lengths, where  and new edges  for  (see Fig. ) and this is denoted by.  is simply called a comb and it is denoted by .

Figure 1.

1.2. Definition 2

A star is a tree with a central node  and  leaves  adjacent to. A star is a complete bipartite graph.

1.3. Definition 3

A bistar  is obtained by joining central nodes  and  of two stars  and  respectively, by an edge.

2. Odd Graceful Labeling of Disjoint Union of Generalized Combs with Stars, Bistars and Paths

This section describes odd graceful labeling for union of generalized combs with stars, bistars and paths.

Theorem 2.1 is odd graceful for  and .

Proof. Let. Then we denote vertex    set and edge set of graph  as follows:

Where and

We define the labeling.

For odd  where  and

For,

For

For even where,  and

For,

For

We can see that the set of edge weights, where  consists of  consecutive odd integers. Therefore  is an odd graceful labeling of.

Theorem 2.2 for  has odd graceful labeling where  and .

Proof. Consider. We have  and, where

and

To show that  is odd graceful we define the labeling

For,  and

For

For

For odd  where  and

For ,

For even  where,  and

For ,

It is easy to see that the set of edge weights of  under the labeling  constitute the following set of  odd consecutive integers  , where. Hence  is an odd graceful labeling of G.

Theorem 2.3 have odd graceful labeling for.

Proof. Consider . We have

And , where

And

To show that G is odd graceful we define the labeling

For

For  and even

For ,

For ,  and odd

For ,

The labeling  produce the set of edge weights consisting of  consecutive odd integers i.e.,, where . Thus  is an odd graceful labeling of graph.

Theorem 2.4  for  and  has odd graceful labeling where.

Proof. Consider.

We have

And

,

Where

And

To show that  is odd graceful we define the labeling

For,  and

For

For

For ,

The set of edge weights of, under the labeling, constitute the following set of consecutive odd integers, where. This proves  to be an odd graceful labeling of.

3. Conclusion

In the present work we investigate new families of odd graceful graphs. To investigate similar results for other graph families and in the context of different labeling techniques is an open area of research.

References

1. M. Baca, C. Barrientos, Graceful and edge-antimagic labeling, Ars Combin., 96(2010),505-513.
2. M. Baca, M. Miller, Super Edge-Antimagic Graphs, Brown Walker Press, (2008).
3. C. Barrientos, Odd-graceful labelings, preprint.
4. P. Eldergill, Decomposition of the Complete Graph with an Even Number of Vertices, M. Sc. Thesis, McMaster University, 1997.
5. J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combinatorics, 17(2014),#DS6
6. Z. Gao, Odd graceful labelings of some union graphs, J. Nat. Sci. Heilongjiang Univ., 24 (2007), 35 -39 .
7. R. B. Gnanajothi, Topics in Graph Theory, Ph. D. Thesis, Madurai Kamaraj University, 1991. S. W. Golomb, How to number a graph, in Graph Theory and Computing, R. C. Read, ed., Academic Press, New York (1972), 23-37.
8. R. L. Graham and N. J. A. Sloane, On additive bases and harmonious graphs, SIAM J. Alg. Discrete Meth., 1 (1980) 382-404.
9. A. Riasat, S. javed and S. Kanwal, On odd graceful labeling of disjoint union of graphs, Utilitas Math., In press.
10. G. Ringel, Problem 25, in Theory of Graphs and its Applications, Proc. Symposium Smolenice 1963, Prague (1964), 162.
11. A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach, N. Y. and Dunod Paris (1967), 349-355.
12. D. B. West, An Introduction to Graph Theory, Prentice-Hall, (1996).

 Contents 1. 1.1. 1.2. 1.3. 2. 3.
Article Tools