A maximally graceful graph is a graceful graph that has the maximum possible number of graceful labelings among all graphs with the same number of vertices.
The numbers of fundamentally distinct graceful labelings for maximally graceful graphs of various types on 
, 2, ... vertices are summarized in the following table and
illustrated above for all simple graphs.
| OEIS | counts | type |
| A379395 | 1, 1, 1, 5, 26, 126, 680, 3876, ... | simple graphs |
| A339892 | 1, 1, 1, 5, 26, 126, 680, 3778, ... | simple graphs with no isolated points |
| 1, 1, 1, 5, 26, 126, 680, 3778, ... | simple connected graphs |
Knuth (2024) considered maximally graceful graphs only among graphs containing no isolated points. Those counts are the same as among
all connected and all simple graphs up to 
, but differ at 
, with the 8-vertex maximally graceful connected (and no-isolated-point)
graph having 3778 (instead of 3876) fundamentally distinct graceful labelings. This
graph is illustrated above. It is significant for also being the 8-vertex graph having
a maximal number (80) of planar embeddings.
Maximally graceful trees are also considered.
See also
Graceful Graph, Graceful Labeling, Maximally Graceful Tree
Explore with Wolfram|Alpha
References
Knuth, D. E. Problem 97, ยง7.2.2.3 in The Art of Computer Programming, Vol. 4B: Combinatorial Algorithms, Part 2. New York: Addison-Wesley, 2022.A339892 and A379395 in "The On-Line Encyclopedia of Integer Sequences."
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Maximally Graceful Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MaximallyGracefulGraph.html