Next: Symmetry
Up: Introduction
Previous: Introduction
A CSP Model for Graceful Graphs
Finding a graceful labelling of a given graph, or proving that one does not exist, can be expressed as a constraint satisfaction problem.
A constraint satisfaction problem consists of:
- a set of variables X = {x1, x2, ..., xn};
- for each variable xi a finite set Di of possible values (its domain);
-
a set of constraints restricting the values that the variables can simultaneously take.
To find a graceful labelling of a graph, a
possible CSP model has a variable for each node,
x1, x2, ..., xn, each with domain
{0, 1, ...,q}
and a variable for each edge,
d1, d2, ... , dq, each with domain
{1, 2, ...,q}.
The constraints of the problem are:
-
if edge k joins nodes i and j then
dk = |xi - xj|;
-
x1, x2, ..., xn are all different;
-
d1, d2, ... , dq are all different.
Specific cases have previously been considered; for instance, the all-interval series problem (problem 007 in [CSPLib]) is equivalent to finding a graceful labelling of a path, and
[Lustig and Puget, 2001] found a graceful labelling of the graph K4 x P2 discussed below.
Next: Symmetry
Up: Introduction
Previous: Introduction
Barbara Smith
January 2003