Relaxing the injectivity constraint on arithmetic and harmonious labelings

Christian Barrientos (Department of Mathematics, Valencia College, Orlando, FL 32832, U.S.A.)
Maged Z Youssef (Department of Mathematics and Statistics, College of Sciences, Al Imam Mohammad Ibn Saud Islamic University, Riyadh 11623, Saudi Arabia, and Department of Mathematics, Faculty of Sciences, Ain Shams University, Cairo 11566, Egypt)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 10, No 2 (2022): Electronic Journal of Graph Theory and Applications

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.