Uniquely Graceful Graph

A uniquely graceful graph is a graph that has exactly one graceful labeling up to graph automorphisms and subtractive complementation. Subtractive complementation replaces each graph vertex label by , where is the number of edges. 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 permutations 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 (2025, Problem 97) enumerates uniquely graceful connected graphs and uniquely graceful simple graphs with no isolated vertices up to 8 vertices.