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?