Odd Graceful Labeling of Acyclic Graphs
Ayesha Riasat^{1}, Sana Javed^{2}
^{1}Mathematics Department, University of Management and Technology, Lahore, Pakistan
^{2}Mathematics Department, Comsats Institute of information Technology, Lahore, Pakistan
Email address:
To cite this article:
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.
Keywords: Odd-Graceful Labeling, Comb, Star, Path, Bistar
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