Abstract

An assignment of integer numbers to the vertices of a given graph under certain conditions is referred to as a graph labeling. The assignment of labels from the set {0,1,2,...,2q-1} to the vertices of G (with n=|V(G)| vertices and q=|E(G)|edges) such that, when each edge has assigned a label defined by the absolute difference of its end-points, the resulting edge labels are {1,3...,2q-1} is referred to as an odd graceful labeling of the graph. In 2000, Kathiresan [13] used the notation Pn;m to denote the graph (spider graph) obtained by identifying the end points of m paths each one has length n , we use the notation Cn;m to denote the graph (closed spider) obtained by identifying the other end points of the graph Pn;m. In this article, we present three algorithms to show how to odd gracefully label the vertices and the edges of the following graphs;P2r+1;m, 1≤ r ≤ 5, m ≥ 2, the closed spider Cn;m, and the graphs obtained by joining one or two paths Pm to each vertex of the path Pn.

References

• A. Brauer, “A problem of additive number theory and its application in electrical engineering,” J. Elisha MitchellScientific SOC., VOl. 61, pp. 55-66, August 1945.
• J. Leech, “On the representation of 1,2,...,n by differences” . J.LondonMath. Soc., vol. 31, pp. 160-169, Apr. 1956.
• A. Rosa, on certain valuations of the vertices of a graph, Theory of Graphs (Internet Symposium,Rome, July 1966), Gordon and Breach, N. Y. and Dunod Paris (1967), 349-355.
• D. Friedman, “Problem 63-12., A Sharp autocorrelation published function,” SIAM Rev., vol. 5, p. 275, July 1963. Solutions and comments, SIAM Rev., vol. 7, pp. 283-284, Apr. 1965; SIAM Rev., vol. 9, pp. 591-593, July 1967.
• L. H. Harper, “DSIF integrated circuit layout and isoperimetric problems”JPL Space Programs summary 37-66, vol. 2, pp. 37-42, Sept. 1970.
• J. C. P. Miller, “Difference bases, three problems in additive number theory,” in Computers in Number Theory, A. D. L. Atkin and B. J. Birch, Eds. London: Academic Press, 1971, pp. 299- 322
• S. W. Golomb, How to number a graph: graph theory and computing, R. C. Read, ed., Academic Press: (1972), 23-37.
• A. Kotazig, On certain vertex valuation of finite graphs, Utilitas Math.4 (1973), 261-290.
• J. A. Bondy, U.S.R. Murty, Graph Theory with Applications, Elsevier North-Holland, 1976.
• Bloom, G. S. and Golomb, S. W. Applications of Numbered Undirected Graphs, Proceedings of the Institute of Electrical and Electronics Engineers 65 (1977) 562570
• R.B. Gnanajothi, Topics in Graph Theory, Ph. D. Thesis, Madurai Kamaraj University, India, (1991).
• P. Eldergill, Decomposition of the Complete Graph with an Even Number of Vertices, M. Sc.Thesis, McMaster University, 1997.
• K. Kathiresan, Two classes of graceful graphs, Ars Combin., 55, (2000), 129-132.
• L. Narayanan. Channel assignment and graph multicoloring, in I. Stojmenovic (Ed.), Handbook of Wireless Networks and Mobile Computing, New York: Wiley, 2001.
• C. Sekar, Studies in Graph Theory, Ph. D. Thesis, Madurai Kamaraj University, 2002.
• M. I. Moussa & E. M. Badr, ODD GRACEFUL LABELINGS OF CROWN GRA PHS, 1st INTERNATIONAL CONFERENCE Computer Science from Algorithms to Applications 2009 Cairo, Egypt.
• J. Gallian, A dynamic survey of graph labeling, The electronic journal of combinatorics 16 (2009), #DS6.
• M. I. Moussa, AN ALGORITHM FOR ODD GRACEFUL LABELING OF THE UNION OF PATHS AND CYCLES, The International Journal on applications of graph Theory in Wireless Ad hoc Networks (GRAPH-HOC) March 2010, Volume 2, Number 1.