5
$\begingroup$

A graceful labeling of a graph with $m$ edges is a labeling of its vertices with some subset of the integers between $0$ and $m$ inclusive, such that no two vertices share a label, and such that each edge is uniquely identified by the positive, or absolute difference between its endpoints.

The Graceful Tree conjecture (all trees are graceful) is a well known open problem.

Finding a graceful labeling seems not so easy; some time ago I made a few tests with a Constraint Programming language and the solver got stuck even for relatively small highly symmetric trees.

A natural variant of the problem is the following:

Graceful Tree Labeling Completion problem: Given a partially labeled tree $T$, is it possible to assign the remaining labels and obtain a graceful labeling?

I'm wondering if there have been attempts to study its complexity?

The conjecture is false for general graphs, furthermore any graph $G$ can be embedded as an induced subgraph of a graceful graph; so the following generalization to graphs could include enough "gears" to allow an NP-complete reduction.

Graceful Graph Labeling Completion problem: Given a partially labeled graph $G$, is it possible to assign the remaining labels and obtain a graceful labeling?

I searched for both, but didn't find anything.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.