#acl EditorsGroup:read,write,admin,delete ChristianDrescher:read,write All:read
= Graceful Graphs =
== Problem Description ==
A graph (V,E) is called a graceful graph if its vertices V can be
labelled with distinct integers from 0 to |E| such that, when each edge
is labelled with the absolute difference between its vertex labels, the
resulting edge labels are all distinct. The task is to determine the
existence of a graceful labelling of a graph.
== Predicates ==
* '''Input''': {{{edge/2}}}
* '''Output''': {{{value/2}}}
== Input format ==
The edges of the graph are provided by instances of the predicate {{{edge/2}}}.
== Output format ==
If a graceful labelling exists, a witness containing vertex labels encoded
in the predicate {{{value/2}}} has to be provided. {{{value(X,I)}}} means the vertex X
is labelled with the unsigned integer I.
== Example(s) ==
The example encodes a clique with 3 nodes:
{{{
edge(a,b). edge(b,c). edge(c,a).
}}}
It is graceful. An assignment of
the values 0, 1, and 3 to the nodes provides a graceful labelling.
Thus, the output of the solver should look like:
{{{
value(a,0). value(b,1). value(c,3).
}}}
Other graceful labellings are also possible.
Additional sample instances: [[https://www.mat.unical.it/aspcomp2013/files/samples/graceful_graphs-sample.zip|download]]
== Problem Peculiarities ==
'''Type''': Search
'''Competition''': Both
'''Complexity''': NP
== Notes and Updates ==
* Feb 2nd, 2013 - Problem Description updated
== Author(s) ==
* Author: Christian Drescher
* Affiliation: NICTA, University of New South Wales, Australia