On the generation of alpha graphs

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. [1] C. Barrientos, S. Barrientos, On graceful supersubdivisions of graphs, Bull. Inst. Combin. Appl. 70 (2014) 77–85.
2. [2] C. Barrientos, S. Minion, Alpha labelings of snake polyominoes and hexagonal chains, Bull. Inst. Combin. Appl. 74 (2015) 73–83.
3. [3] C. Barrientos, S. Minion, New attack on Kotzig’s conjecture, Electron. J. Graph Theory Appl. 4(2) (2016) 119–131.
4. [4] C. Barrientos, S. Minion, Snakes and caterpillars in graceful graphs, J. Algorithms and Comput. 50(2) (2018) 37–47.
5. [5] G. Chartrand, L. Lesniak, Graphs & digraphs, 4th Edition. CRC Press, Boca Raton (2005).
6. [6] J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2020) #DS6.
7. [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. [8] D. Jungreis, M. Reid, Labeling grids, Ars Combin. 34 (1992) 167–182.

9. [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. [10] A. Kotzig, On certain vertex valuations of finite graphs, Util. Math. 4 (1973) 67–73.
11. [11] S. C. López, F. A. Muntaner-Batle, Graceful, harmonious and magic type labelings: relations and techniques, Springer (2017).
12. [12] M. Maheo, H. Thuillier, On d-graceful graphs, Ars Combin. 13 (1982) 181–192.
13. [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. [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. [15] A. Rosa, Labelling snakes, Ars Combin. 3 (1977) 67–74.
16. [16] A. Rosa, J. Širán, Bipartite labelings of trees and the gracesize, J. Graph Theory 19(2) (1995) 201–215.
17. [17] G. Sethuraman, P. Selvaraju, Gracefulness of arbitrary supersubdivisions of graphs, Indian J. Pure Appl. Math. 32 (2001) 1059–1064.
18. [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. [19] B. Yao, X. Liu, M. Yao, Connections between labellings of trees, Bull. Iranian Math. Soc. 43(2) (2017) 275–283.