Graceful Labeling
A graceful labeling (or graceful numbering) is a special graph labeling of a graph on 
edges in which the nodes are labeled with a subset of distinct nonnegative integers from 0 to 
and the graph edges are labeled with the absolute differences between node values. If the resulting graph edge numbers run from 1 to 
inclusive, the labeling is a graceful labeling and the graph is said to be a graceful graph.
Not all graphs possess a graceful labeling; those that do not are said to be ungraceful.
Some gracefully numbered graphs are illustrated above.
The vertex labels must include 0 and 
. This can be seen since the edge labels must contain 
, but the only way to form an absolute difference of 
from two vertex labels each between 0 and 
inclusive is for one to be 0 and the other to be 
. Furthermore, the vertices bearing labels 0 and 
must be adjacent for the same reason.
If a set of labels 
form a graceful labeling for a graph, then so do the labels 
. Therefore, with the exception of the singleton graph 
, all graceful graphs have an even number of graceful labelings.
"Fundamentally different" graceful labelings (cf. Gardner 1983, p. 164) refer to labelings that are distinct modulo subtractive complementation and the symmetries of the graph (i.e., the graph automorphism group). For example, while there are a large number of graceful labelings of the icosahedral graph, there are only a small number of fundamentally different ones (cf. Gardner 1983, pp. 163-164, who reported a computation producing 5 fundamentally different labelings; the actual number seems to be 24).
There exist graphs whose vertices can be labeled with distinct nonnegative integers such that graph edge numbers run from 1 to 
, but where the maximum vertex number must exceed 
. Since such graphs violate the maximum allowed vertex label in the definition of gracefulness, they are ungraceful. An example of such a graph is the disjoint union 
of the path graph 
and claw graph 
, illustrated above. While there appears to be no standard term for such graphs in the literature, they might be termed "excessively graceful."
Graceful labelings may be generated using perfect rulers, i.e., rulers of integer length 
with the minimum possible numbers of marks so that all distances 1 to 
can be measured.
There are 
graceful labelings for graphs on 
graph edges having no isolated points corresponding to the Lehmer encodings of the 
permutations of 
(Sheppard 1976), although some of these correspond to alternate labelings of the same graph. The numbers of nonisomorphic graceful graphs with no isolated points on 
edges for 
, 2, ... are 1, 1, 3, 5, 12, 37, 112, 340, 1078, 3620, 12737, ... (OEIS A308544), while the numbers of connected graceful graphs on 
edges are 1, 1, 3, 5, 11, 28, 79, 227, 701, 2302, 8071, ... (OEIS A308545).
Golomb showed that the number of graph edges connecting the even-numbered and odd-numbered sets of nodes is 
, where 
is the number of graph edges.
The following table summarizes the numbers of fundamentally distinct graceful labelings. Arumugam and Bagga (2011) give (total) counts for the cycle graph 
up to 
, though typographical errors are present for 
and 23.
| class |
OEIS |
counts |
antiprism graph  |
A000000 |
X, X, 1, 26, 20, ... |
| Apollonian network |
|
1, 33,, ... |
| barbell graph |
|
X, X, 1, 0, 0, ... |
| book graph |
|
1, 16, 0, 417, ... |
| centipede graph |
A000000 |
1, 1, 4, 30, 232, 2058, 26654, ... |
complete bipartite graph  |
A335619 |
1, 1, 1, 4, 1, 7, 2, 10, 3, ... |
complete graph  |
|
1, 1, 1, 1, 0, 0, 0, 0, 0, 0, ... |
complete tripartite graph  |
A339891 |
1, 4, 7, 12, 20, 34, 74, 131, 260, ... |
complete tripartite graph  |
|
1, 1, 0, 0, 0, 0, 0, ... |
crown graph  |
A000000 |
0, 0, 0, 27, 69, X, 0, ... |
cycle graph  |
A000000 |
X, X, 1, 1, 0, 0, 6, 12, 0, 0, 104, 246, 0, 0, 3882, ... |
| dipyramidal graph |
|
X, X, 4, 1, 7, 0, 22, X, X, 0, ... |
empty graph  |
|
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... |
| gear graph |
A000000 |
X, X, 34, 358, 6781, 231758, 10575203, 695507601, ... |
grid graph  |
A000000 |
1, 1, 358, 47428572, ... |
grid graph  |
|
1, 27, ... |
| halved cube graph |
|
1, 1, 1, 0, ... |
| Hanoi graph |
|
1, 140, ... |
| helm graph |
|
X, X, 109, 777, ... |
hypercube graph  |
A000000 |
1, 1, 27, 607173, ... |
 king graph |
|
1, 1, 154, ... |
 knight graph |
|
1, 0, 12, ... |
ladder graph  |
A000000 |
1, 1, 16, 177, 2242, 48068, ... |
Möbius ladder  |
A000000 |
X, X, 1, 34, 750, 8451, 208882, 5371997, 207664885, ... |
| pan graph |
A000000 |
X, X, X, 5, 8, 13, 30, 60, 160, 394, 924, 2434, 7178, 21446, ... |
path complement graph  |
A000000 |
1, 0, 0, 1, 13, 34, 45, 18, 1, ... |
path graph  |
A000000 |
1, 1, 1, 1, 2, 6, 8, 10, 30, 74, 162, 332, 800, 2478, 6398, 13980, ... |
prism graph  |
A000000 |
X, X, 4, 27, 444, ... |
star graph  |
A000012 |
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... |
| sun graph |
A000000 |
X, X, 0, 204, 4765, ... |
| sunlet graph |
A000000 |
X, X, 9, 42, 255, 2283, 27361, ... |
triangular snake graph  |
|
1, 1, 0, 0, 368, ... |
| web graph |
|
X, X, 894, ... |
wheel graph  |
A000000 |
X, X, 1, 4, 12, 23, 67, 251, 1842, 10792, ... |
REFERENCES
Arumugam, S. and Bagga, J. "Graceful Labeling Algorithms and Complexity-A Survey." J. Indonesian Math. Soc., Special edition, 1-9, 2011.
Gardner, M. "Mathematical Games: The Graceful Graphs of Solomon Golomb, or How to Number a Graph Parsimoniously." Sci. Amer. 226, No. 3, 108-113, March 1972.
Gardner, M. "Golomb's Graceful Graphs." Ch. 15 in Wheels, Life, and Other Mathematical Amusements. New York: W. H. Freeman, pp. 152-165, 1983.
Golomb, S. W. "How to Number a Graph." In Graph Theory and Computing (Ed. R. C. Read). New York: Academic Press, pp. 23-37, 1972.
Knuth, D. E. §7.2.2.3 in The Art of Computer Programming, Vol. 4B. In preparation, 2020.Sheppard, D. A. "The Factorial Representation of Balanced Labelled Graphs." Discr. Math. 15, 379-388, 1976.
