Applications of mathematical programming in graceful labeling of graphs

[摘要] Graceful labeling is one of the best known labeling methods ofgraphs. Despite the large number of papers published on thesubject of graph labeling, there are few particular techniques to be used by researchers to gracefully label graphs. In this paper,first a new approach based on the mathematical programmingtechnique is presented to model the graceful labeling problem.Then a “branching method” is developed to solve the problem forspecial classes of graphs. Computational results show theefficiency of the proposed algorithm for different classes ofgraphs. One of the interesting results of our model is in theclass of trees. The largest tree known to be graceful has at most27 vertices but our model can easily solve the graceful labelingfor trees with 40 vertices.

[学科分类] 应用数学