Independent Vertices Inserted Graph of Grid and Leftmost Child Joined Graph of a Subdivided Extreme-Sides Leave Tree are Graceful
A graceful labeling of a graph G with n edges is an injection f : V (G) → {0, 1, 2, . . . , n} with the property that the resulting edge labels are distinct where an edge incident with the vertices u and v is assigned the label |f(u) − f(v)|. The main focus of graph labeling is essentially understanding the nature of graceful graphs. The characterization of graceful graphs is one of the most difficult problems in graph theory. In this paper two new classes of graceful graphs are obtained using the graph operation, called insertion of independent vertices in a graph. More precisely, for every grid graph Pm¤Pn, with m, n ≥ 2, the independent vertices inserted graph G*(Pm¤Pn) of Pm¤Pn is shown to be graceful. Also for a given extreme-sides leave tree T, the independent vertices inserted graph of leftmost child joined graph of the subdivided extreme-sides leave tree, denoted [LC(Tˆ)]* is also shown to be graceful.