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 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 fundmanetally different labelings; the actual number seems to be 24).

The total number of graceful labelings of all simple graphs on , 2, ... nodes are 1, 2, 16, 144, 1428, 25328, 631026, 25087224, ... (OEIS A333727; E. Weisstein, Apr. 3 and Jul. 30, 2020).

Interestingly, most small graphs seem to have a number of labelings satisfying . Of all ungraceful simple graphs on 8 of fewer vertices, 1872 have , while 11291 have . Of the graphs with having between 2 and 7 nodes (to exclude the special case ), all are apex graphs, asymmetric, class 1, cyclic, identity, noneulerian, and weakly perfect. The smallest value for graphs on 8 or fewer vertices (other than ) having is , which occurs for the single graph on 6 nodes illustrated above.

There also 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 graceful labelings (including those that are symmetry-equivalent or subtractive complements). Arumugam and Bagga (2011) give counts for the cycle graph up to , though typographical errors are present for and 23.

class	OEIS	counts
antiprism graph	A326576	X, X, 96, 832, 8080, ...
Apollonian network		48, 396, ...
barbell graph		X, X, 16, 0, 0, ...
book graph		16, 128, 0, 40032, ...
centipede graph	A334351	2, 4, 16, 120, 928, 8232, 106616, ...
complete bipartite graph	A337793	2, 16, 144, 9216, 57600, 14515200, ...
complete graph		1, 2, 12, 48, 0, 0, 0, 0, 0, 0, ...
complete tripartite graph	A334307	12, 32, 168, 1152, 9600, 97920, 1491840, 21127680, ...
complete tripartite graph		12, 96, 0, 0, 0, 0, 0, ...
crown graph	A326747	X, X, 0, 2592, 33120, ...
cycle graph	A333720	X, X, 12, 16, 0, 0, 168, 384, 0, 0, 0, 4576, 11808, ...
dipyramidal graph		X, X, 96, 96, 280, 0, 1232, ...
empty graph		1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
gear graph	A337795	X, X, 408, 5728, 135620, 5562192, 296105684, ...
grid graph	A337796	1, 16, 5728, 758857152, ...
grid graph		1, 2592, ...
Hanoi graph		12, 1680, ...
helm graph		X, X, 1308, 12432, ...
hypercube graph	A338005	2, 16, 2592, 466308864, ...
king graph		1, 0, 384, ...
knight graph		1, 48, 2464, ...
ladder graph	A333719	2, 16, 128, 1416, 17936, ...
Möbius ladder	A337794	X, X, 144, 1088, 30000, 405648, 11697392, ...
pan graph	A333729	X, X, X, 20, 32, 52, 120, 240, 640, 1576, 9736, ...
path complement graph	A336428	1, 0, 0, 4, 52, 136, 180, 72, 4, ...
path graph	A006967	1, 2, 4, 4, 8, 24, 32, 40, 120, 296, 648, ...
prism graph	A336677	X, X, 96, 2592, 17760, ...
star graph	A098558	1, 2, 4, 12, 48, 240, 1440, 10080, 80640, ...
sun graph	A337792	X, X, 0, 3264, 95300, ...
sunlet graph	A333757	X, X, 108, 672, 5100, 54792, ...
triangular snake graph		1, 12, 0, 0, 5888, ...
web graph		X, X, 10728, ...
wheel graph	A333672	X, X, X, 48, 64, 240, 552, 1876, 8032, 66312, ...

Wolfram Web Resources