TOPICS
Search

Graceful Labeling


GracefulGraphs

A graceful labeling (or graceful numbering) is a special graph labeling of a graph on m edges in which the nodes are labeled with a subset of distinct nonnegative integers from 0 to m and the graph edges are labeled with the absolute differences between node values. If the resulting graph edge numbers run from 1 to m 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 m. This can be seen since the edge labels must contain m, but the only way to form an absolute difference of m from two vertex labels each between 0 and m inclusive is for one to be 0 and the other to be m. Furthermore, the vertices bearing labels 0 and m must be adjacent for the same reason.

If a set of labels (l_1,l_2,...,l_k) form a graceful labeling for a graph, then so do the labels (m-l_1,m-l_2,...,m-l_k). Therefore, with the exception of the singleton graph K_1, 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).

UnrestrictedGracefulGraph

There exist graphs whose vertices can be labeled with distinct nonnegative integers such that graph edge numbers run from 1 to m, but where the maximum vertex number must exceed m. 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 P_3 union K_(1,3) of the path graph P_3 and claw graph K_(1,3), 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 n with the minimum possible numbers of marks so that all distances 1 to n can be measured.

There are m! graceful labelings for graphs on m graph edges having no isolated points corresponding to the Lehmer encodings of the m! permutations of (0,1,...,m-1) (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 m edges for m=1, 2, ... are 1, 1, 3, 5, 12, 37, 112, 340, 1078, 3620, 12737, ... (OEIS A308544), while the numbers of connected graceful graphs on e 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 |_(m+1)/2_|, where m 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 C_n up to n=24, though typographical errors are present for n=16 and 23.

classOEIScounts
antiprism graph Ci_(2n)(1,2)A000000X, X, 1, 26, 20, ...
Apollonian network1, 33,, ...
barbell graphX, X, 1, 0, 0, ...
book graph1, 16, 0, 417, ...
centipede graphA0000001, 1, 4, 30, 232, 2058, 26654, ...
complete bipartite graph K_(n,n)A3356191, 1, 1, 4, 1, 7, 2, 10, 3, ...
complete graph K_n1, 1, 1, 1, 0, 0, 0, 0, 0, 0, ...
complete tripartite graph K_(1,1,n)A3398911, 4, 7, 12, 20, 34, 74, 131, 260, ...
complete tripartite graph K_(n,n,n)1, 1, 0, 0, 0, 0, 0, ...
crown graph K_2 square K_n^_A0000000, 0, 0, 27, 69, X, 0, ...
cycle graph C_nA000000X, X, 1, 1, 0, 0, 6, 12, 0, 0, 104, 246, 0, 0, 3882, ...
dipyramidal graphX, X, 4, 1, 7, 0, 22, X, X, 0, ...
empty graph K^__n1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
gear graphA000000X, X, 34, 358, 6781, 231758, 10575203, 695507601, ...
grid graph P_n square P_nA0000001, 1, 358, 47428572, ...
grid graph P_n square P_n square P_n1, 27, ...
halved cube graph1, 1, 1, 0, ...
Hanoi graph1, 140, ...
helm graphX, X, 109, 777, ...
hypercube graph Q_nA0000001, 1, 27, 607173, ...
n×n king graph1, 1, 154, ...
n×n knight graph1, 0, 12, ...
ladder graph P_2 square P_nA0000001, 1, 16, 177, 2242, 48068, ...
Möbius ladder M_nA000000X, X, 1, 34, 750, 8451, 208882, 5371997, 207664885, ...
pan graphA000000X, X, X, 5, 8, 13, 30, 60, 160, 394, 924, 2434, 7178, 21446, ...
path complement graph P^__nA0000001, 0, 0, 1, 13, 34, 45, 18, 1, ...
path graph P_nA0000001, 1, 1, 1, 2, 6, 8, 10, 30, 74, 162, 332, 800, 2478, 6398, 13980, ...
prism graph P_2 square C_nA000000X, X, 4, 27, 444, ...
star graph S_nA0000121, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
sun graphA000000X, X, 0, 204, 4765, ...
sunlet graphA000000X, X, 9, 42, 255, 2283, 27361, ...
triangular snake graph TS_(2n-1)1, 1, 0, 0, 368, ...
web graphX, X, 894, ...
wheel graph W_nA000000X, X, 1, 4, 12, 23, 67, 251, 1842, 10792, ...

See also

Graceful Graph, Graceful Permutation, Labeled Graph, Perfect Ruler, Ungraceful Graph

Explore with Wolfram|Alpha

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: Combinatorial Algorithms, Part 2. New York: Addison-Wesley, 2022.Sheppard, D. A. "The Factorial Representation of Balanced Labelled Graphs." Discr. Math. 15, 379-388, 1976.

Cite this as:

Weisstein, Eric W. "Graceful Labeling." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GracefulLabeling.html

Subject classifications