Graceful Graphs

Problem Description

A graph (V,E) is called a graceful graph if its vertices V can be labelled with distinct unsigned integers, its edges E can be labelled with the absolute differences between vertex labels, and the edge labels are in the range {1..|E|}. The task is to determine the existence of a graceful labelling of a graph.

The edges of the graph are provided by instances of the predicate edge/2. 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.

Predicates

• Input: edge/2

• Output: value/2

Input format

Output format

Example(s)

Problem Peculiarities

Type: Search Competition: Both Complexity: NP

Notes and Updates

Author(s)

• Author: Christian Drescher
  • Affiliation: NICTA, University of New South Wales, Australia