On the generation of alpha graphs
DOI:
https://doi.org/10.13069/jacodesmath.1111733Keywords:
$\alpha$-labeling, Graceful graph, Amalgamation, Duplication, ReplicationAbstract
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.
Received: 3 February 2021 | Accepted: 22 October 2021Downloads
References
C. Barrientos and S. Barrientos, On graceful supersubdivisions of graphs, Bull. Inst. Combin. Appl. 70 (2014) 77–85.
C. Barrientos and S. Minion, Alpha labelings of snake polyominoes and hexagonal chains, Bull. Inst. Combin. Appl. 74 (2015) 73–83.
C. Barrientos and S. Minion, New attack on Kotzig's conjecture, Electron. J. Graph Theory Appl. 4(2) (2016) 119–131.
C. Barrientos and S. Minion, Snakes and caterpillars in graceful graphs, J. Algorithms Comput. 50(2) (2018) 37–47.
G. Chartrand and L. Lesniak, Graphs & Digraphs, 4th Edition, CRC Press, Boca Raton (2005).
J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2020) #DS6.
S. W. Golomb, How to number a graph, in: R. C. Read (Ed.), Graph Theory and Computing, Academic Press, New York (1972) 23–37.
D. Jungreis and M. Reid, Labeling grids, Ars Combin. 34 (1992) 167–182.
V. J. Kaneria, S. K. Vaidya, G. V. Ghodasara, and S. Srivastav, Some classes of disconnected graceful graphs, in: Proceedings of the First International Conference on Emerging Technologies and Applications in Engineering, Technology and Sciences (2008) 1050–1056.
A. Kotzig, On certain vertex valuations of finite graphs, Util. Math. 4 (1973) 67–73.
S. C. López and F. A. Muntaner-Batle, Graceful, Harmonious and Magic Type Labelings: Relations and Techniques, Springer, Cham (2017).
M. Maheo and H. Thuillier, On $d$-graceful graphs, Ars Combin. 13 (1982) 181–192.
G. Ringel, Problem 25, in: Theory of Graphs and its Applications, Proc. Symposium Smolenice 1963, Czech. Acad. Sci., Prague (1964) 162.
A. Rosa, On certain valuations of the vertices of a graph, in: Theory of Graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach, New York and Dunod, Paris (1967) 349–355.
A. Rosa, Labelling snakes, Ars Combin. 3 (1977) 67–74.
A. Rosa and J. Širáň, Bipartite labelings of trees and the gracesize, J. Graph Theory 19(2) (1995) 201–215.
G. Sethuraman and P. Selvaraju, Gracefulness of arbitrary supersubdivisions of graphs, Indian J. Pure Appl. Math. 32(7) (2001) 1059–1064.
P. J. Slater, On $k$-graceful graphs, in: Proceedings of the 13th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. 36 (1982) 53–57.
B. Yao, X. Liu, and M. Yao, Connections between labellings of trees, Bull. Iranian Math. Soc. 43(2) (2017) 275–283.
