6
$\begingroup$

In the below grid all 18 orthogonal differences are distinct, with a difference of 18 missing.

Rook 3x3 difference grid

Could the highest number be 18? The resulting graph would have valence 4, making it an Eulerian Graceful graph with edges(mod 4)=2. Rosa (1967) proved Eulerian Graceful graphs must have edges(mod 4)=0 or 3, so 18 is impossible.

Thus the minimal $3\times3$ rook difference grid has $rdg(3,3)=19$.

For $rdg(1,n)$ see Golomb Ruler.

$rdg(2,3)=9$ and $rdg(2,4)=16$, as shown below.

rook difference grids 2x3 and 2x4

What are values for larger grids?

$\endgroup$
2
$\begingroup$

I used a depth first search written in C to find the following:

$rdg(3,4)=30$, so the $3\times4$ rook graph is graceful.

\begin{array}{|c|c|c|c|} \hline 0 & 1 & 9 & 30 \\ \hline 16 & 29 & 2 & 19 \\ \hline 22 & 3 & 27 & 7 \\ \hline \end{array}

$rdg(4,4)=48$, so the $4\times4$ rook graph is also graceful.

\begin{array}{|c|c|c|c|} \hline 0 & 1 & 23 & 47 \\ \hline 19 & 44 & 9 & 2 \\ \hline 37 & 42 & 3 & 11 \\ \hline 48 & 4 & 36 & 32 \\ \hline \end{array}

$rdg(3,5)=46$. This is not graceful. Like the $3\times3$, Rosa (1967) shows this is the minimum possible. \begin{array}{|c|c|c|c|c|} \hline 0 & 1 & 10 & 26 & 46 \\ \hline 23 & 45 & 37 & 5 & 8 \\ \hline 42 & 14 & 44 & 38 & 3\\ \hline \end{array}

Misha Lavrov's answer, gives a graceful labeling of the $2\times5$ rook graph, but larger $2\times n$ rook graphs cease being graceful:

$rdg(2,6)=38$. The $2\times6$ rook graph has $36$ edges. \begin{array}{|c|c|c|c|c|c|} \hline 0 & 1 & 10 & 16 & 34 & 38 \\ \hline 35 & 32 & 24 & 37 & 5 & 12\\ \hline \end{array}

$rdg(2,7)=53$. The $2\times7$ rook graph has $49$ edges. \begin{array}{|c|c|c|c|c|c|c|} \hline 0 & 6 & 16 & 24 & 38 & 41 & 53 \\ \hline 31 & 52 & 3 & 51 & 12 & 8 & 1 \\ \hline \end{array}

$\endgroup$
  • $\begingroup$ Wow, nice finds! Can you also extend this to Queen graphs? $\endgroup$ – Ed Pegg Jun 23 at 15:34
  • $\begingroup$ In theory, yes. It's just a matter of specifying the edge connections. In practice, maybe not. A $4\times4$ queen graph has $76$ edges, compared to $48$ for the rook graph, and the queen graph lacks the regularity of the rook graph. The search space increases significantly as the complexity of the graph increases, so there's no guarantee that a solution can be found in a reasonable amount of time. Other search methods are possible, of course. $\endgroup$ – nickgard Jun 23 at 18:37
4
$\begingroup$

Here is a graceful labeling of the $2\times 5$ grid, so $rdg(2,5)=25$:

\begin{array}{|c|c|c|c|c|} \hline 0 & 6 & 7 & 21 & 25 \\ \hline 24 & 22 & 19 & 11 & 2 \\ \hline \end{array}

I put together a simulated annealing setup for graceful-labeling type problems after your previous question, and I'll try it at some larger grids next to see if I get anywhere.

For the $3\times 4$ grid, the following labeling proves $rdg(3,4) \in \{30,31\}$ but doesn't quite settle the question:

\begin{array}{|c|c|c|c|} \hline 0 & 3 & 14 & 22 \\ \hline 27 & 9 & 4 & 29 \\ \hline 31 & 18 & 30 & 1 \\ \hline \end{array}

$\endgroup$
  • $\begingroup$ Just found that solution slightly later than you did, and proved it's unique ignoring row/column permutations and the 25-% complement. $\endgroup$ – Ed Pegg Jun 14 at 16:39

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.