Open Access
Subscription Access
Open Access
Subscription Access
Independent Vertices Inserted Graph of Grid and Leftmost Child Joined Graph of a Subdivided Extreme-Sides Leave Tree are Graceful
Subscribe/Renew Journal
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.
Keywords
Graceful Labeling, Insertion of Independent Vertices, Leftmost Child Joined Graph.
Subscription
Login to verify subscription
User
Font Size
Information
- G. S. Bloom and S. W. Golomb, Applications of numbered undirected graphs, Proc. IEEE, 65 (1977), 562–570.
- C. Delorme, Two sets of graceful graphs, J. Graph Theory, 4 (1980), 247–250.
- S. W. Golomb, How to number a graph, Graph Theory and computing, R.C. Reed, ed., Academic press, Newyork (1972), 23–37.
- J. A. Gallian, A dynamic survey of graph labeling, Electronic Journal of combinatorics, 19 (2015), DS6.
- A. Kotzig, Decompositions of a complete graph into 4k-gons (in Russian), Mstematicky Casopis, 15 (1965), 229–233.
- G. Ringel, Problem 25, in Theory of Graphs and its Applications: Proceedings of the Symposium Smolenice Prague (1964), 162.
- A. Rosa, On certain valuations of the vertices of a graph, Theory of graphs, International Symposium, Rome, Dunod, Paris (1967), 349–355.
- M. A. Seoud and M. Z. Youssef, The effect of some operations on labeling of graphs, Proc. Math. Phys. Soc. Egypt, 73 (2000), 35–49.
- G. Sethuraman and P. Selvaraju, Gracefulness of arbitrary supersubdivision of graphs, Indian Journal of Pure and Applied Mathematics, 32(7) (2001), 1059–1064.
Abstract Views: 295
PDF Views: 0