Graceful Graphs and Graceful Labelings: Two Mathematical Programming Formulations and Some Other New Results
Timothy Redl · Rice Research Repository (Rice University) · 2003
Given a graph G consisting of vertices and edges, a vertex labeling of G is an assignment f of labels to the vertices of Gthat produces for each edge xy a label depending on the vertex labels f(x) and f(y). A vertex labeling f is called a graceful labeling of a graph G with e edgesif f is an injection from the vertices of G to the set {0, 1, ..., e} such that when each edge xy is assigned the label |f(x) - f(y)| the resulting edge labels are distinct. A graph G is called graceful if there exists a graceful labeling of G. In this paper we present two mathematical programming formulations of the graceful labeling problem (first as an integer programming problem, second as a constraint programming problem), along with some new results on the gracefulness of three classes of graphs: generalized graphs, double cones, and a particular class of product graphs.