On the generation of alpha graphs

  • Christian Barrientos
Keywords: {$\alpha$}-labeling, Graceful graph, Amalgamation, Duplication, Replication


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.


C. Barrientos, S. Barrientos, On graceful supersubdivisions of graphs, Bull. Inst. Combin. Appl. 70 (2014) 77–85.

C. Barrientos, S. Minion, Alpha labelings of snake polyominoes and hexagonal chains, Bull. Inst. Combin. Appl. 74 (2015) 73–83.

C. Barrientos, S. Minion, New attack on Kotzig’s conjecture, Electron. J. Graph Theory Appl. 4(2) (2016) 119–131.

C. Barrientos, S. Minion, Snakes and caterpillars in graceful graphs, J. Algorithms and Comput. 50(2) (2018) 37–47.

G. Chartrand, 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, R. C. Read (Editor), Graph theory and computing, Academic Press, New York (1972) 23-37.

D. Jungreis, M. Reid, Labeling grids, Ars Combin. 34 (1992) 167–182.

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.

A. Kotzig, On certain vertex valuations of finite graphs, Util. Math. 4 (1973) 67–73.

S. C. López, F. A. Muntaner-Batle, Graceful, harmonious and magic type labelings: relations and techniques, Springer (2017).

M. Maheo, 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, Czech. (1964) 162. On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966)

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.

A. Rosa, Labelling snakes, Ars Combin. 3 (1977) 67–74.

A. Rosa, J. Širán, Bipartite labelings of trees and the gracesize, J. Graph Theory 19(2) (1995) 201–215.

G. Sethuraman, P. Selvaraju, Gracefulness of arbitrary supersubdivisions of graphs, Indian J. Pure Appl. Math. 32 (2001) 1059–1064.

P. J. Slater, On k-graceful graphs, Proc. of the 13th S. E. Conf. on Combinatorics, Graph Theory and Computing (1982) 53–57.

B. Yao, X. Liu, M. Yao, Connections between labellings of trees, Bull. Iranian Math. Soc. 43(2) (2017) 275–283.