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

Similarly, is the Shrikhande Graph graceful?

• Is Paley 9 known not to be graceful? Jun 15, 2019 at 5:47
• @FabioSomenzi The Paley 9 graph is also the 3x3 rook graph. It is not graceful. See this other question by Ed Pegg for an explanation: math.stackexchange.com/q/3262295/420432 Jun 29, 2019 at 6:13
• @nickgard Thanks! Jul 3, 2019 at 7:30

## 1 Answer

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

• What is the edge list for it? Jun 11, 2019 at 16:51
• The first list is given as the cyclical vertices. Each label is connected to the ones at distance $1,3,4,9,10$ and $12$ steps further round in the cycle. Jun 11, 2019 at 16:57
• Wow! How did you find this? Jun 11, 2019 at 19:03
• A depth first search of the possible vertex values. I can limit the search space a little because $0$ and $39$ must be connected. Backtrack as soon as a known edge value is not unique. Fortunately it didn't need to search far. The search started at $0-1-3\dots$ and the first solution was at $0-1-5\dots$ I'm checking the Shrikhande Graph now, but that's much harder. Jun 11, 2019 at 19:43
• You should submit a paper to a journal (that does covers) with the title "Paley-13 is Graceful." Just your name and a picture. Jun 12, 2019 at 14:14