Harmonious graphs from α-trees

Abstract

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 P_n, the join of a graph G and tK₁ 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: K_n, m ∪ K_{1, 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.