Graceful Labeling in the Context of Duplication of Graph Elements

Abstract

Let a simple graph G = ((V (G), E(G)) be connected and undirected graph with p vertices and q edges. Let f be a function from the set of vertices to the set of integer {0,1 , 2, 3,…, q} and let f* be a function from the set of edge to the set of positive integer {1, 2, 3,…, q} defined as

f*(uv) = |f(u) − f(v)|

for all u,v∈V (G) and uv∈E(G) . A function f is called graceful labeling of a graph G if f is injective and f* is bijective. The graph G which admits graceful labeling f is called a graceful graph. In this paper, we find graceful labeling for some new graphs results from the duplication of graph elements and then we prove that the new graphs are graceful.

Article Details

Section
Research Articles

References

Rosa, A. (1967). On certain valuations of the vertices of a graph. (In Theory of Graphs, International Symposium, Rome, July, 1966), New York: Gordon and Breach.

Golomb, S. W. (1972). How to number a graph. In R. C. Read (Ed.). Graph Theory and Computing. 23–37. New York, U.S.A. Academic Press.

Cattell, R. (2007). Graceful labellings of paths. Discrete Mathematics, 307(24), 3161–3176.

Kaneria, V. J., Makadia, H. M., & Jariya, M. M. (2014). Graceful labeling for cycle of graph. International Journal of Mathematics Research, 6(2), 173–178.

Boxwala, S. A., & Vashishta, P. (2015). Some new families of graceful graphs. Electronic Notes in Discrete Mathematics, 48, 127–133.

Koh, K. M., Phoon, L. Y., & Soh, K. W. (2015). The gracefulness of the join of graphs (II). AKCE International Journal of Graphs and Combinatorics, 12(2-3) 180–185.

Hegde, S. M., & Kumudakshi. (2016). Forther results on graceful directed graphs. Electronic Notes in Discrete Mathematics, 53, 149–154.

Khatun, S., & Nayeem, A. (2017). Graceful labeling of some zero divisor graphs. Electronic Notes in Discrete Mathematics, 63, 189–196.

Ragukumar, P., & Sethuraman, G. (2018). Binomial trees are graceful, AKCE International Journal of Graphs and Combinatorics, In Press.

Wang, T. M., & Zhang, G. H. (2018). On edge–graceful labeling and deficiency for regular graphs. AKCE International Journal of Graphs and Combinatorics, 15 (1), 105–111.