Graceful Graphs / Almost Graceful Graphs

Created: Mar 1, 1993; last updated: May 21, 2014

Consider the connection between graceful graphs and Golomb rulers. This can be thought of as a kind of covering problem – pairwise absolute distances between marks on the ruler (a subset of the integers {0, …, N}) should completely cover the integer range {1, …, N}. What happens if we loosen the covering so that there are some gaps? Or tighten the covering so that the edge labels fall within an even smaller set of integers?

These possibilities motivate the following extension of graceful labelings:

Given a graph on N edges, choose vertex labels from the set {0, …, N+k} for some k. Continue to calculate edge labels as the absolute differences of their vertex labels, and continue to require that the edge labels be distinct. However, allow the edge labels to cover only a subset of the integers {1, …, N+k}. If a graph admits such a labeling, call the graph k-almost-graceful.

Conjecture (Brundage, 1994):

Every graph G is k-almost-graceful for some \(k \ge 0\).

Clearly, 0-almost-graceful is the same as graceful. Also, every k-almost-graceful labeling is also (k+1)-almost-graceful. One can ask many questions about k-almost-graceful graphs. Here are a few:

• Given a graph G, how can one calculate the least k for which it is k-almost-graceful? Or determine lower and upper bounds for k.
• Observe that k can be negative! In that case, there is an even tighter covering. Which graphs are k-almost-graceful for negative k?
• For each k, how many graphs are k-almost-graceful up to isomorphism?