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 distinct" or "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). Consider the star graph . There a 12 graceful labelings: ((0, 1, 2, 3), (0, 1, 3, 2), (0, 2, 1, 3), (0, 2, 3, 1), (0, 3, 1, 2), (0, 3, 2, 1), (3, 0, 1, 2), (3, 0, 2, 1), (3, 1, 0, 2), (3, 1, 2, 0), (3, 2, 0, 1), and (3, 2, 1, 0). As is clear from the figure above, these occur when the center is 0 or 3 and the remaining numbers can be arranged in any way among the tips, giving possibilities ( to account for possible permutations of 3 numbers among the tips and the factor of 2 since that can be done in two ways: with 0 in the center or with 3 in the center). Since all the tips are equivalent by the symmetry of the graph and interchanging 0 and 3 corresponds to subtractive complementation, there is a unique fundamental graceful labeling for . In fact, star graphs are in general uniquely graceful by similar arguments to those above.

For a graph other than and , the total number of labelings is related to the number of fundamentally distinct labelings of a graph by

where is the order of the graph automorphism group. For example, while there are a large number (5760) of unrestricted graceful labelings of the icosahedral graph, there are only 24 fundamentally different ones (correcting the count of 5 reported by Gardner 1983, pp. 163-164).

The total number of all (not just fundamental) graceful labelings of all simple graphs on , 2, ..., 8 nodes were computed by E. Weisstein on Apr. 3 and Jul. 30, 2020. Knuth (2024, Problem 97) gave the corresponding total counts of fundamentally distinct labelings. These counts, together with total counts of fundamental graceful labelings for all simple graphs, are given in the table below.

OEIS	total of all labelings on , 2, ... vertices	total type
A333727	1, 2, 16, 144, 1428, 25328, 631026, 25087224, ...	all (not just fundamental) graceful labelings
A379576	1, 1, 2, 14, 174, 3655, 122439, 6470268, ...	fundamental graceful labelings
A379575	0, 1, 2, 13, 157, 3292, 110578, 5903888, ...	fundamental graceful labelings of graphs with no isolated points

Graceful labelings may be generated using sparse rulers (cf. Pegg 2019).

There are graceful labelings for graphs on graph edges having no isolated points corresponding to the Lehmer encodings of the permutations of (Sheppard 1976; Knuth 2024, p. 23), 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 for some indexed families of graphs. 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, 8, 1, 42, 2, 7, 7, ...
complete graph		1, 1, 1, 1, 0, 0, 0, 0, 0, 0, ...
complete tripartite graph	A000000	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	A000000	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, ...

A graph that contains a single fundamentally distinct graceful labeling (i.e., a unique labeling modulo the graph automorphism group and with respect to subtractive complementation) may be termed a uniquely graceful graph, and a graph possessing the maximum possible number of fundamentally distinct labelings (possibly subject to some additional condition such as possessing no isolated vertices) may be termed a maximally graceful graph.