The 13-node Paley graph has vertices 1 to 13 that are connected by an edge when their difference is one of the values $(1,3,4,9,10,12)$.
Is Paley-13 a graceful graph? Can the 13 vertices be labeled with values from 0 to 39 so that the edges have differences 1 to 39?
Paley-13 is also a toroidal graph, if that helps. Here's a graceful labeling for the $9_{123}$ circulant graph.
Similarly, is the Shrikhande Graph graceful?
Both the Paley-13 graph and the Shrikhande graph are graceful.
The following is a graceful labeling for the Paley-13 graph:
$0,1,5,39,23,34,13,3,21,7,38,33,24$
For verification, here are the absolute differences at distance $1,3$ and $4$, cycling as necessary, demonstrating that all differences $1$ to $39$ appear once:
$1,4,34,16,11,21,10,18,14,31,5,9,24$
$39,22,29,26,20,13,6,35,12,17,38,32,19$
$23,33,8,36,2,27,25,30,3,7,37,28,15$
Shrikhande graph:
Both labelings were found using a depth first search with backtracking, written in C.
Searches were stopped when a solution was found, so it's not known whether other graceful labelings are possible.
Edit: I found a second graceful labeling for the Shrikhande graph:
$0,1,6,39,2,47,32,14,46,12,5,8,29,42,28,48$.