Harmonious graphs from α-trees

Christian Barrientos, Sarah Minion


Two of the most studied graph labelings are the types of harmonious and graceful. A harmonious labeling of a graph of size m and order n, is an injective assignment of nonnegative integers smaller than m, such that the weights of the edges, which are defined as the sum of the labels of the end-vertices, are distinct consecutive integers after reducing modulo m. When n = m + 1, exactly two vertices of the graph have the same label. An α-labeling of a tree of size m is a bijective assignment of nonnegative integers, not larger than m, such that the labels on one stable set are smaller than the labels on the other stable set, and the weights of the edges, which are defined as the absolute difference of the labels of the end-vertices, are all distinct; this is the most restrictive type of graceful labeling. Even when these labelings are significantly different in their definitions of the weight, for certain kinds of graphs, there is a deep connection between harmonious and α-labelings. We present new families of harmoniously labeled graphs built on α-labeled trees. Among these new results there are three families of trees, the kth power of the path Pn, the join of a graph G and tK1 where G is a graph that admits a more restrictive type of harmonious labeling and its order is different of its size by at most one unit. We also prove the existence of two families of disconnected harmonius graphs: Kn, m ∪ K1, m − 1 and G ∪ T, where G is a unicyclic graph and T is a tree built with α-trees. In addition, we show that almost all trees admit a harmonious labeling.


$\alpha$-labeling, harmonious, strongly felicitous

Full Text:


DOI: http://dx.doi.org/10.5614/ejgta.2021.9.2.9


C. Barrientos, On additive vertex labelings, Indonesian Journal of Combinatorics, 4(1) (2020), 34–52.

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

L.C. Chen, On harmonious Labelings of the Amalgamation of Wheels, Masters Thesis, Chung Yuan Christian University, Taiwan.

R. Figueroa-Centeno, R. Ichishima, and F. Muntaner-Batle, Labeling the vertex amalgamation of graphs, Discuss. Math. Graph Theory, 23 (2003), 129–139.

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

R.B. Gnanajothi, Topics in Graph Theory, Ph. D. Thesis, Madurai Kamaraj University, 1991.

T. Grace, On sequential labelings of graphs, J. Graph Theory, 7 (1983) 195–201.

R.L. Graham and N.J.A. Sloane, On additive bases and harmonious graphs, SIAM J. Alg. Discrete Methods, 1 (1980) 382–404.

B. Liu and X. Zhang, On harmonious labelings of graphs, Ars Combin., 36 (1993) 315–326.

S.C. Lopez and F.A. Muntaner-Batle, ´ Graceful, Harmonious and Magic Type Labelings: Relations and Techniques, Springer, Cham, 2017.

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

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.

P. Selvaraju and G. Sethurman, Decomposition of complete graphs and complete bipartite graphs into copies of P3n or S2(P3n) and harmonious labeling of K2 + Pn, J. Indones. Math. Soc., Special Edition (2011) 109–122.

M.A. Seoud, A.E.I. Abdel Maqsoud and J. Sheehan, Harmonious graphs, Util. Math., 47 (1995) 225–233.

M.A. Seoud and M.Z. Youssef, The effect of some operations on labeling of graphs, Proc. Math. Phys. Soc. Egypt, 73 (2000) 35–49.

S.C. Shee, On harmonious and related graphs, Ars Combin., 23 (1987) A, 237–247.

J. Yuan and W. Zhu, Some results on harmonious labelings of graphs, J. Zhengzhou Univ. Nat. Sci. Ed., 30 (1998) 7–12.

M.Z. Youssef, Note on even harmonious labeling of cycles, Util. Math., 100 (2016) 137–142.


  • 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