Is Paley-13 a graceful graph? 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. ![graceful toroidal]( 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$

![Paley 13 graph graceful labelling](

* * *

Shrikhande graph: ![Shrikhande graph graceful labelling](

* * *

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$.