A uniquely graceful graph is a graph that has exactly one fundamentally distinct graceful labeling. Uniquely graceful graphs
for ,
..., 7, are illustrated above.
There exists a uniquely graceful graph on 12 vertices (the fourth of the smallest graceful octic graphs in the numbering of GraphData) which is also an identity graph, meaning it has a unique graceful labeling even among permutation of labels (though of course not counting subtractive complementation). Such graphs might be termed identically uniquely graceful.
The numbers of uniquely graceful graphs of various types on , 2, ... vertices are summarized in the following table.
Knuth (2024, Problem 97) enumerates uniquely graceful simple graphs in the connected
and no isolated point cases up to 8 vertices.
OEIS | counts | type |
A379574 | 1, 1, 2, 5, 2, 5, 11, 33, ... | simple graphs |
A379572 | 0, 1, 2, 4, 1, 5, 10, 29, ... | simple graphs with no isolated points |
A379573 | 1, 1, 2, 4, 1, 4, 2, 19, ... | simple connected graphs |