4
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Is Paley 9 known not to be graceful? $\endgroup$
    – Fabio Somenzi
    Jun 15, 2019 at 5:47
  • $\begingroup$ @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 $\endgroup$
    – nickgard
    Jun 29, 2019 at 6:13
  • $\begingroup$ @nickgard Thanks! $\endgroup$
    – Fabio Somenzi
    Jul 3, 2019 at 7:30

1 Answer 1

Reset to default
7
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ What is the edge list for it? $\endgroup$
    – Ed Pegg
    Jun 11, 2019 at 16:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – nickgard
    Jun 11, 2019 at 16:57
  • $\begingroup$ Wow! How did you find this? $\endgroup$
    – Ed Pegg
    Jun 11, 2019 at 19:03
  • 4
    $\begingroup$ 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. $\endgroup$
    – nickgard
    Jun 11, 2019 at 19:43
  • 1
    $\begingroup$ You should submit a paper to a journal (that does covers) with the title "Paley-13 is Graceful." Just your name and a picture. $\endgroup$
    – Ed Pegg
    Jun 12, 2019 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.