An algorithm for finding a feasible solution of graph labeling problems
Abstract
A labeling (or valuation) of a graph G = (V, E) is a map that carries graph elements to numbers (usually to the positive or non-negative integers). The two famous labeling methods are called graceful labeling and edge-magic total labeling. A function f is called a graceful labeling of graph G with m edges if f is an injection from the vertices of G to the set {0, 1,...,m} such that when each edge (x, y) is assigned the label |f(x) - f(y)|, the resulting edge labels are distinct. An edge-magic total labeling is another well-known labeling that was motivated by the notion of magic squares in number theory. Despite the large number of papers published on the subject of graph labeling, there are few general techniques available for determining whether an arbitrary graph has a labeling. In this paper, first integer programming models of graceful labeling and edge-magic total labeling are presented. The existence of a feasible solution of the presented model implies that the given graph has graceful or edge-magic labeling respectively. Therefore, an algorithm based on branch and bound procedure is developed to find a feasible solution for each model. Then the algorithm has been extensively tested on a variety of classes of randomly generated graphs. The computational results show our model can easily solve the graceful labeling and edge-magic total labeling for large size graphs, especially for trees with 50 vertices.
