Absolutely k-Harmonious Labeling of Product Graphs

Source abstract

Graph labeling assigns integers to vertices, edges, or both of a graph subject to prescribed balance conditions, and has broad applications in coding theory, network design, and communication protocols. In this paper we study the absolutely k-harmonious labeling (ABH labeling) of product graphs. A vertex labeling assigns to every vertex an integer label drawn from the residues modulo k, and every edge is then given an induced label formed from the absolute difference between the sum of its two endpoint labels and k, reduced modulo k. A labeling is called absolutely k-harmonious if, across all label classes, the vertex counts carrying each label differ from one another by at most one, and the edge counts carrying each label likewise differ by at most one. We prove that the absolutely k-harmonious property is preserved under three principal graph product operations ? the Cartesian product, the tensor product, and the strong product ? of two absolutely k-harmonious graphs, provided suitable divisibility conditions hold. We further prove that the property is preserved under graph complementation, when the order and the size of the graph are each divisible by k, and under disjoint union. Concretely, we establish that grid graphs formed as Cartesian products of two paths, and complete bipartite graphs whose part sizes sum to a multiple of three, are absolutely 3-harmonious for all suitable orders. All theorems are derived rigorously from the defining balance conditions and each is accompanied by a fully worked numerical example. The restriction to the case k equal to 3 for concrete graph families is natural because the modulo-3 cyclic structure aligns with the ternary residue classes of path indices, and extensions to larger values of k are identified as directions for future research.