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.