#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