Alpha graphs with different pendent paths

Christian Barrientos


Graceful labelings are an effective tool to find cyclic decompositions of complete graphs and complete bipartite graphs. The strongest kind of graceful labeling, the α-labeling, is in the center of the research field of graph labelings, the existence of an α-labeling of a graph implies the existence of several, apparently non-related, other labelings for that graph. Furthermore, graphs with α-labelings can be combined to form new graphs that also admit this type of labeling. The standard way to combine these graphs is to identify every vertex of a base graph with a vertex of another graph. These methods have in common that all the graphs involved, except perhaps the base, have the same size. In this work, we do something different, we prove the existence of an α-labeling of a tree obtained by attaching paths of different lengths to the vertices of a base path, in such a way that the lengths of the pendent paths form an arithmetic sequence with difference one, where consecutive vertices of the base path are identified with paths which lengths are consecutive elements of the sequence. These α-trees are combined in several ways to generate new families of α-trees. We also prove that these trees can be used to create unicyclic graphs with an α-labeling. In addition, we show that the pendent paths can be substituted by equivalent α-trees to produce new α-trees, obtaining in this manner a quite robust category of α-trees.


α-labeling, graceful graph, unicyclic graph

Full Text:




C. Barrientos, Graceful labelings of chain and corona graphs, Bull. Inst. Combin. Appl. 34 (2002) 17--26.

C. Barrientos, On graceful chain graphs, Util. Math. 78 (2009) 55--64.

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

G. Chartrand and L. Lesniak, Graphs & Digraphs 4th ed. CRC Press, Boca Raton, FL 33487 (2005).

R. Figueroa-Centeno, R. Ichishima, F. Muntaner-Batle, and A. Oshima, Gracefully cultivating trees on a cycle, Electron. Notes Discrete Math. 48 (2015) 143--150.

J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2019), #DS6.

F. Harary and A.J. Schwenk, The number of caterpillars, Discrete Math. 6 (1973), 359--365.

C. Huang, A. Kotzig, and A. Rosa, Further results on tree labellings, Util. Math. 21c (1982) 31--48.

R. Ichishima, F.A. Muntaner-Batle, and A. Oshima, The consecutively super edge-magic deficiency of graphs and related concepts, Electron. J. Graph Theory Appl. 8 (1) (2020), 181--194.

K.M. Koh, D.G. Rogers, and T. Tan, Products of graceful trees, Discrete Math. 31 (1980) 279--292.

S.C. Lopez 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.

M. Mavronicolas and L. Michael, A substitution theorem for graceful trees and its applications, Discrete Math. 309 (2009) 3757--3766.

D. Mishra, S.K. Rout, and P.C. Nayak, Some new graceful generalized classes of diameter six trees, Electron. J. Graph Theory Appl. 5 (1) (2017), 181--194.

R.C. Read and R.J. Wilson, An Atlas of Graphs, Oxford University Press, Oxford, England, 1998.

A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach, N. Y. and Dunod Paris (1967) 349--355.

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

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

R. Stanton and C. Zarnke, Labeling of balanced trees, Proc. 4th Southeast Conf. Combin., Graph Theory, Comput. (1973) 479--495.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats