Relaxing the injectivity constraint on arithmetic and harmonious labelings
Abstract
Several of the most studied graph labelings are injective functions, this constraint precludes some graphs from admitting such labelings; a well-known example is given by the family of trees that cannot be harmoniously labeled. In order to study the existence of these labelings for certain graphs, the injectivity constraint is often dropped. In this work we eliminate this condition for two different, but related, additive vertex labelings such as the harmonious and arithmetic labelings. The new labelings are called semi harmonious and semi arithmetic. We consider some families of graphs that do not admit the injective versions of these labelings, among the graphs considered here we have cycles and other cycle-related graphs, including the analysis of some operations like the Cartesian product and the vertex or edge amalgamation; in addition, we prove that all trees admit a semi harmonious labeling. Something similar is done with the concept of arithmetic labeling, studying finite unions of semi arithmetic graphs together with some general results.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2022.10.2.13
References
B.D. Acharya and S.M. Hegde, Arithmetic graphs, J. Graph Theory 14 (1990), 275–299.
C. Barrientos and E. Krop, Improved bounds for relaxed graceful trees, Graphs Combin. 33 (2017), 287–305.
C. Barrientos and S. Minion, New advances in Kotzig’s conjecture, Fundamental J. Math. Appl. 2(2) (2019), 186–194.
C. Bu and J. Shi, A class of (k, d)-arithmetic graphs, J. Harbin Eng. Univ. 16 (1995), 79–81.
G.J. Chang, D.F. Hsu, and D.G. Rogers, Additive variations on a graceful theme: some results on harmonious and other related graphs, Congr. Numer. 32 (1981), 181–197.
G. Chartrand and L. Lesniak-Foster, Graphs & Digraphs, 3rd Edition, CRC Press, 1996.
R.J. Faudree, M.S. Jacobson, J. Lehel, and R.H. Schelp, Irregular networks, regular graphs and integer matrices with distinct row and column sums, Discrete Math. 76 (1989), 223–240.
J.A. Gallian, A dynamic survey of graph labeling, 24th edition, Elect. J. Combin. (2021).
K.A. Germina, More on classes of strongly indexable graphs, European J. Pure and Applied Math. 3(2) (2010), 269–281.
R.L. Graham and N.J.A. Sloane, On additive bases and harmonious graphs, SIAM J. Alg. Discrete Methods 1 (1980), 382–404.
D. Jungreis and M. Reid, Labeling grids, Ars Combin. 34 (1992), 167–182.
S.M. Lee, E. Schmeichel, and S.C. Shee, On felicitous graphs, Discrete Math. 93 (1991), 201–209.
A. Lourdusamy and M. Seenivasan, Vertex equitable labeling of graphs, J. Discrete Math. Sci, Crypt. 11 (2008), 727–735.
X. Lu, W. Pan, and X. Li, k-gracefulness and arithmetic of graph St(m)∪Kp, q, J. Jilin Univ. 42 (2004), 333–336.
M.Z. Youssef, Two general results on harmonious labelings, Ars Combin. 68 (2003), 225–230.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.