Graceful Graphs and Graceful Labelings: Two Mathematical Programming Formulations and Some Other New Results

摘要

Given a graph G consisting of vertices and edges, a vertex labeling of G is an assignment f of labels to the vertices of G that 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 edges if 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 (see Figure 1). 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 Petersen graphs P(n,k), double cones C_n + K_2, and product graphs of the form K_4 x P_n.