Symmetry in Graceful Graphs

Our investigations of graceful graphs have focussed on graphs with symmetry, because our research is concerned with methods for eliminating symmetry in CSPs.

There are two kinds of symmetry in the CSP model representing the problem of finding a graceful labelling of a graph: first, there may be symmetry in the graph. For instance, if the graph is a clique, any permutation of the node labels in a graceful labelling is also graceful. If the graph is a path, P_n, the node labels can be reversed to give an equivalent labelling. The second type of symmetry is that we can replace every node label i by its complement q - i. We can also combine each graph symmetry with the complement symmetry. For instance, the graceful labelling (0, 3, 1, 2) of P₄ has three symmetric equivalents: reversal (2, 1, 3, 0); complement (3, 0, 2, 1); and reversal + complement (1, 2, 0, 3).

In finding all graceful labellings of a graph by finding all solutions of the CSP, we do not want to find two labellings that are symmetrically equivalent (by a graph isomorphism, or by taking the complement, or both). Symmetry in the CSP also causes wasted search effort: the search may explore partial assignments that are symmetric to assignments already considered. In fact, in many cases, it is essential to eliminate, or at least reduce, this wasted search in order to be able to find even one solution to the CSP.

To eliminate symmetry in the CSP, we have either added constraints to the CSP model to eliminate symmetrically equivalent solutions, or used Symmetry Breaking During Search [Gent and Smith, 2000], or a combination of these methods. SBDS adds constraints during the search for solutions, on backtracking to a choice point. We have also used a more recent version [Gent et al., 2002] which combines SBDS with GAP (Groups, Algorithms and Programming) [GAP, 2002]: GAP-SBDS allows the symmetry group of the problem, rather than its elements, to be described.

We have used the constraint programming systems ILOG Solver and ECLⁱPS^e. The original SBDS was implemented in ILOG Solver; GAP-SBDS is implemented in ECLⁱPS^e. Neither of these implementations are generally available, but an SBDS library is included in the latest release of ECLⁱPS^e.