welcome: please sign in

Upload page content

You can upload content for the page named below. If you change the page name, you can also upload content for another page. If the page name is empty, we derive the page name from the file name.

File to load page content from
Page name
Comment

location: GracefulGraphs

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 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: download

Problem Peculiarities

Type: Search Competition: Both Complexity: NP

Notes and Updates

Author(s)