On additive vertex labelings
Abstract
In a quite general sense, additive vertex labelings are those functions that assign nonnegative integers to the vertices of a graph and the weight of each edge is obtained by adding the labels of its end-vertices. In this work we study one of these functions, called harmonious labeling. We calculate the number of non-isomorphic harmoniously labeled graphs with n edges and at most n vertices. We present harmonious labelings for some families of graphs that include certain unicyclic graphs obtained via the corona product. In addition, we prove that all n-cell snake polyiamonds are harmonious; this type of graph is obtained via edge amalgamation of n copies of the cycle C3 in such a way that each copy of this cycle shares at most two edges with other copies. Moreover, we use the edge-switching technique on the cycle C4t to generate unicyclic graphs with another type of additive vertex labeling, called strongly felicitous, which has a solid bond with the harmonious labeling.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.19184/ijc.2020.4.1.5
References
G. Agnarsson and R. Greenlaw, Graph Theory: Modeling, Applications, and Algorithms, Pearson, (2006).
M. Baca and M. Miller, Super Edge-Antimagic Graphs: A Wealth of Problems and Some Solutions, BrownWalker Press, 2007, Boca Raton, FL, USA
C. Barrientos, Graceful graphs with pendant edges, Australas. J. Combin. 33 (2005) 99--107.
C. Barrientos and S. Minion, Snakes: from graceful to harmonious, Bull. Institute Combin. Appl., 79 (2017) 95--107.
C. Barrientos, https://oeis.org/A005418, 2018.
C. Barrientos, https://oeis.org/A329910, 2019.
C. Barrientos, Special graceful labelings of irregular fences and lobsters, Universal Journal of Mathematics and Applications, 2 (1) (2019) 1--10.
C. Barrientos and S. Minion, Counting and labeling grid related graphs, Electronic Journal of Graph Theory and Applications, 7 (2) (2019), 349--363.
R. Cattell, Graceful labellings of paths, Discrete Math., 307 (2007) 3161--3176.
G. J. Chang, D. F. Hsu, and D. G. Rogers, Additive variations on a graceful theme: some results on harmonious and other related graphs, Cong. Numer., 32 (1981), 181--197.
G. Chartrand and L. Lesniak, Graphs & Digraphs 4th ed. CRC Press (2005).
R. Figueroa-Centeno, R. Ichishima, and F. Muntaner-Batle, The place of super edgemagic labelings among other classes of labelings, Discrete Math., 231 (2001) 153--168.
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.
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.
A. Kotzig, On certain vertex valuations of finite graphs, Util. Math., 4 (1973) 67--73.
B. Liu and X. Zhang, On a conjecture of harmonious graphs, Systems Science and Math. Sciences, 4 (1989) 325--328.
S. C. Lopez and F. A. Muntaner-Batle, Graceful, Harmonious and Magic Type Labelings: Relations and Techniques, Springer, Cham, 2017.
J. Renuka, P. Balaganesan, P. Selvaraju, On harmonious labeling, Internat. J. Advance in Math. Math. Sci., 1(2) (2012) 65--70.
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.
M. A. Seoud, A. E. I. Abdel Maqsoud and J. Sheehan, Harmonious graphs, Util. Math., 47 (1995) 225--233.
G. Sethuraman, V. Murugan, Generating graceful unicyclic graphs from a given forest, to appear in AKCE Int. J. of Graphs and Combinatorics.
M. Truszcyński, Graceful unicyclic graphs, Demonstratio Mathematica, 17 (1984), 377-387.
W. D. Wallis, Magic Graphs, Birkhauser, Boston, 2001.
Y. Yang, W. Lu, and Q. Zeng, Harmonious graphs C_{2k} cup C_{2j+1}, Util. Math., 62 (2002) 191--198.
M. Z. Youssef, Two general results on harmonious labelings, Ars Combin., 68 (2003) 225--230.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.