The Graceful Labeling on W Graph

Wed Giyarti, Kiki A. Sugeng, Fery Firmansah

Abstract

Let G be a graph with vertex set V = V (G) and edge set E = E(G). Graceful labeling is an injective function g from the vertex set V to a set of number {0,1,2,…,|E|} which induces a bijective function g^' from the set E to the set of number {0,1,2,…,|E|}, where for each edge uvE with u,vV applies g'(uv) = |g(u)-g(v)|. A graph with graceful labeling is called a graceful graph. This research aims to construct a new graph, namely a W graph, and prove that the W graph is graceful. W graph is a graph constructed from two ladder graphs and one C3 graph, where C3 is formed by connecting the end vertices of each ladder, for example, v1 and x1, and by adding a vertex connected to the vertices v1 and x1. In this paper, the authors show that the W graph satisfies the graceful labeling so that the W graph is graceful.

Keywords: graceful labeling, graph labeling, W graph.


Full Text:

PDF


References


BAPAT RB. Graphs and Matrices, Newyork: Springer London Dordrecht Heidelberg, 2010, 9-10.

ROSA A. On certain valuations of the vertices of a graph. Theory of Graphs. Internat. Symposium. Rome: Gordon and Breach, NY and Dunod Paris, 1966, 349-355.

https://www.researchgate.net/publication/244474213_On_certain_valuations_of_the_vertices_of_a_graph.

GALLIAN JA. A dynamic survey of graph labeling. Electronic Journal of Combinatorics, 2020, 23(DinamicSurveys):DS6. https://www.combinatorics.org/files/Surveys/ds6/ds6v23-2020.pdf.

CATTELL R. Graceful labeling of paths. Discrete Mathematics, 2007, 307(24): 3161-3176. https://doi.org/10.1016/j.disc.2007.03.046.

GRAF A. Graceful labeling of pendant graphs. Rose-Hulman Undergraduate Mathematics Journal, 2014, 15(1): 158-172. https://scholar.rose-hulman.edu/rhumj/vol15/iss1/10.

BARRIENTOS C. Graceful graph with pendant edges. Australasian Journal of Combinatorics, 2005, 33(1): 99-107. https://ajc.maths.uq.edu.au/pdf/33/ajc_v33_p099.pdf.

AKERINA A, SUGENG KA. Graceful labeling on a multiple-fan graph with pendants. AIP Conference Proceedings, 2021, 2326(1): 020001. https://doi.org/10.1063/5.0039411.

SANTHAKUMARAN AP, BALAGANESAN P. Vertex graceful labeling of some classes of graphs. Proyecciones (Antofagasta), 2018, 37(1): 19-43. http://dx.doi.org/10.4067/S0716-09172018000100019.

MANULANG JM, SUGENG KA. Graceful labeling on torch graph. Indonesian Journal of Combinatorics, 2018, 2(1): 14-19. http://dx.doi.org/10.19184/ijc.2018.2.1.2.

ANICK D. Counting graceful labelings of trees: A theoretical and empirical study. Discrete Applied Mathematics, 2016, 198: 65-81. https://doi.org/10.1016/j.dam.2015.05.031.

LAU G, SHIU WC, NG H. Further results on super graceful labeling of graphs. AKCE International Journal of Graphs and Combinatorics, 2016, 13: 200-209. https://doi.org/10.1016/j.akcej.2016.06.002.


Refbacks

  • There are currently no refbacks.