The Graceful Coalescence of Alpha Cycles

Year 2019, Volume: 2 Issue: 2, 114 - 120, 27.06.2019

Christian Barrientos , Sarah Minion

https://doi.org/10.33434/cams.505485

Abstract

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.

Keywords

Coalescence, $\alpha$-labeling, Graceful labeling, Ladder

References

• [1] A. Rosa, J. Siran, Bipartite labelings of trees and the gracesize, J. Graph Theory, 19 (1995), 201-215.
• [2] M. Maheo, H. Thuillier, On d-graceful graphs, Ars Combin., 13 (1982), 181-192.
• [3] P. J. Slater, On k-graceful graphs, Proceedings of the 13th Southeastern International Conference on Combinatorics, Graph Theory and Computing, (1982), 53-57.
• [4] C. Barrientos, Graceful labelings of chain and corona graphs, Bull. Inst. Combin. Appl., 34 (2002), 17-26.
• [5] C. Barrientos, S. Minion, Alpha labelings of snake polyominoes and hexagonal chains, Bull. Inst. Combin. Appl., 74 (2015), 73-83.
• [6] G. Chartrand, L. Lesniak, Graphs & Digraphs, 2nd ed. Wadsworth & Brooks/Cole, 1986.
• [7] J. A. Gallian, A dynamic survey of graph labeling, Electronic J. Combin., 21(#DS6), 2018.
• [8] 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.
• [9] J.-F. Sloane, https://oeis.org/A277504, 2016.
• [10] 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.
• [11] K. Kathiresan, Subvisions of ladders are graceful, Indian J. Pure Appl. Math., 23 (1992), 21-23.