Using the coalescence and another similar technique, it is proven that some subdivisions of the ladder $L_n = P_2 \times P_n$ also admit an $\alpha$-labeling, extending and generalizing the existing results for this type of subdivided graphs.
📌 3 Key Takeaways
🎯
Objective & Hypothesis:The standard coalescence of two graphs is extended, allowing to identify two isomorphic subgraphs instead of a single vertex.
📊
Key Findings & Data:It is proven here that any succesive coalescence of cycles of size $n$, where $n$ is divisible by four, results in an $\alpha$-graph, that is, the most restrictive kind of graceful graph, when the subgraphs identified are paths of sizes not exceeding $\frac{n}{2}$.
💡
Conclusion & Impact:Using the coalescence and another similar technique, it is proven that some subdivisions of the ladder $L_n = P_2 \times P_n$ also admit an $\alpha$-labeling, extending and generalizing the existing results for this type of subdivided graphs.
The standard coalescence of two graphs is extended, allowing to identify two isomorphic subgraphs instead of a single vertex. It is proven here that any succesive coalescence of cycles of size $n$, where $n$ is divisible by four, results in an $\alpha$-graph, that is, the most restrictive kind of graceful graph, when the subgraphs identified are paths of sizes not exceeding $\frac{n}{2}$. Using the coalescence and another similar technique, it is proven that some subdivisions of the ladder $L_n = P_2 \times P_n$ also admit an $\alpha$-labeling, extending and generalizing the existing results for this type of subdivided graphs.
A. Rosa, J. Siran, Bipartite labelings of trees and the gracesize, J. Graph Theory, 19 (1995), 201-215
M. Maheo, H. Thuillier, On d-graceful graphs, Ars Combin., 13 (1982), 181-192
P. J. Slater, On k-graceful graphs, Proceedings of the 13th Southeastern International Conference on Combinatorics, Graph Theory and Computing, (1982), 53-57
C. Barrientos, Graceful labelings of chain and corona graphs, Bull. Inst. Combin. Appl., 34 (2002), 17-26
C. Barrientos, S. Minion, Alpha labelings of snake polyominoes and hexagonal chains, Bull. Inst. Combin. Appl., 74 (2015), 73-83
G. Chartrand, L. Lesniak, Graphs & Digraphs, 2nd ed. Wadsworth & Brooks/Cole, 1986
J. A. Gallian, A dynamic survey of graph labeling, Electronic J. Combin., 21(#DS6), 2018
A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (International Symposium, Rome, July 1966), Gordon and Breach, N. Y. and Dunod Paris (1967), 349-355
B. D. Acharya, M. K. Gill, On the index of gracefulness of a graph and the gracefulness of two-dimensional square lattice graphs, Indian J. Math., 23 (1981), 81-94
K. Kathiresan, Subvisions of ladders are graceful, Indian J. Pure Appl. Math., 23 (1992), 21-23.