Volume 3, Issue 3-1, June 2015, Page: 14-18
Odd Graceful Labeling of Acyclic Graphs
Ayesha Riasat, Mathematics Department, University of Management and Technology, Lahore, Pakistan
Sana Javed, Mathematics Department, Comsats Institute of information Technology, Lahore, Pakistan
Received: May 28, 2015;       Accepted: May 30, 2015;       Published: Jun. 10, 2015
DOI: 10.11648/j.ajam.s.2015030301.13      View  4416      Downloads  122
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
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
Reference
[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).
Browse journals by subject