On the generation of alpha graphs

Year 2022, , 31 - 43, 13.05.2022

Christian Barrientos

https://doi.org/10.13069/jacodesmath.1111733

Cited By: 1

Abstract

Graceful labelings constitute one of the classical subjects in the area of graph labelings; among them, the most restrictive type are those called {$\alpha$}-labelings. In this work, we explore new techniques to generate {$\alpha$}-labeled graphs, such as vertex and edge duplications, replications of the entire graph, and $k$-vertex amalgamations. We prove that for some families of graphs, it is possible to duplicate several vertices or edges. Using $k$-vertex amalgamations we obtain an {$\alpha$}-labeling of a graph that can be decomposed into multiple copies of a given {$\alpha$}-labeled graph as well as a robust family of irregular grids that can {$\alpha$}-labeled.

Keywords

{$\alpha$}-labeling, Graceful graph, Amalgamation, Duplication, Replication

References

• [1] C. Barrientos, S. Barrientos, On graceful supersubdivisions of graphs, Bull. Inst. Combin. Appl. 70 (2014) 77–85.
• [2] C. Barrientos, S. Minion, Alpha labelings of snake polyominoes and hexagonal chains, Bull. Inst. Combin. Appl. 74 (2015) 73–83.
• [3] C. Barrientos, S. Minion, New attack on Kotzig’s conjecture, Electron. J. Graph Theory Appl. 4(2) (2016) 119–131.
• [4] C. Barrientos, S. Minion, Snakes and caterpillars in graceful graphs, J. Algorithms and Comput. 50(2) (2018) 37–47.
• [5] G. Chartrand, L. Lesniak, Graphs & digraphs, 4th Edition. CRC Press, Boca Raton (2005).
• [6] J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2020) #DS6.
• [7] S. W. Golomb, How to number a graph, R. C. Read (Editor), Graph theory and computing, Academic Press, New York (1972) 23-37.
• [8] D. Jungreis, M. Reid, Labeling grids, Ars Combin. 34 (1992) 167–182.
• [9] V. J. Kaneria, S. K. Vaidya, G. V. Ghodasara, S. Srivastav, Some classes of disconnected graceful graphs, Proc. First Internat. Conf. Emerging Technologies and Appl. Engin. Tech. Sci. (2008) 1050–1056.
• [10] A. Kotzig, On certain vertex valuations of finite graphs, Util. Math. 4 (1973) 67–73.
• [11] S. C. López, F. A. Muntaner-Batle, Graceful, harmonious and magic type labelings: relations and techniques, Springer (2017).
• [12] M. Maheo, H. Thuillier, On d-graceful graphs, Ars Combin. 13 (1982) 181–192.
• [13] G. Ringel, Problem 25, in: Theory of graphs and its applications, Proc. Symposium Smolenice 1963, Czech. Acad. Sci., Prague, Czech. (1964) 162. On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966)
• [14] A. Rosa, On certain valuations of the vertices of a graph, theory of graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach NY and Dunod Paris (1967) 349–355.
• [15] A. Rosa, Labelling snakes, Ars Combin. 3 (1977) 67–74.
• [16] A. Rosa, J. Širán, Bipartite labelings of trees and the gracesize, J. Graph Theory 19(2) (1995) 201–215.
• [17] G. Sethuraman, P. Selvaraju, Gracefulness of arbitrary supersubdivisions of graphs, Indian J. Pure Appl. Math. 32 (2001) 1059–1064.
• [18] P. J. Slater, On k-graceful graphs, Proc. of the 13th S. E. Conf. on Combinatorics, Graph Theory and Computing (1982) 53–57.
• [19] B. Yao, X. Liu, M. Yao, Connections between labellings of trees, Bull. Iranian Math. Soc. 43(2) (2017) 275–283.