Graceful Graphs / Almost Graceful Graphs
Updated: 21 May 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 kalmostgraceful.
Clearly, 0almostgraceful is the same as graceful. Also, every kalmostgraceful labeling is also (k+1)almostgraceful. One can ask many questions about kalmostgraceful graphs. Here are a few:

Given a graph G, how can one calculate the least k for which it is kalmostgraceful? 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 kalmostgraceful for negative k?

For each k, how many graphs are kalmostgraceful up to isomorphism?