# Four Dimensional Rook Domination

Let $\gamma(G)$ denote the domination number of a graph, and $G\,\square\,H$ denote the cartesian product of two graphs. Then $K_8\,\square\, K_8$ is the rook graph, whose vertices are the squares of a chessboard, with edges between squares a rook can move between. We can similarly define the rook graph of any square chessboard as $K_n \,\square \, K_n$, and define $d$-dimensional chessboards as $(K_n)^{\square \,d}$, where generalized rooks move by sliding parallel to one of the coordinate axes.

Clearly, $\gamma(K_n\,\square\, K_n)=n$. Put another way, it is possible to place $n$ rooks on an $n\times n$ chessboard so every square contains a rook or is attacked by one, while $n-1$ rooks are insufficient. Much less easily, you can prove $\gamma(K_n\,\square\,K_n\,\square\,K_n)=\lceil n^2/2\rceil$, which also has an interpretation with rooks on a 3D board.

These nice answers for two and three dimensions gave me hope there was a nice one for 4, so my question is this:

Is anything known about $\gamma ((K_n)^{\square \,4})$? Or, how many rooks does it takes to dominate an $n\times n\times n \times n$ chessboard?

It's easy to show that $\gamma ((K_2)^{\square \,4})= 4$, and not hard to show $\gamma ((K_3)^{\square \,4})= 9$. But for a $4\times 4\times 4\times 4$ board, all I know is that the domination number is at least 23 and at most 32. Unfortunately, it is infeasible to brute force $\gamma((K_4)^{\square \,4})$.

• Burchett has a couple of papers on $k$-tuple domination on the rook's graph. I haven't seen the papers, and they are (indexed but) not reviewed in Math Reviews, so I don't know whether they are at all relevant. The references are Congr Numer 199 (2009) 187-204 and 209 (2011) 179-187. – Gerry Myerson Jun 28 '15 at 23:49
• Those papers I don't think are relevant to regular domination on higher dimensional rook's graphs, but the results for k- or k-tuple domination might be able to be extended to higher dimensions. – Paul Burchett Jul 30 '15 at 15:06

This might be an answer for n=4. There are 24 points. I think 23 is impossible. Just a guess, however.

   0   0   0   0
0   0   0   1
0   1   1   2
0   2   2   3
0   2   3   3
0   3   1   2
1   0   1   3
1   1   2   0
1   1   3   1
1   2   0   2
1   3   2   1
1   3   3   0
2   0   2   2
2   0   3   2
2   1   0   3
2   2   1   0
2   2   1   1
2   3   0   3
3   0   1   3
3   1   2   1
3   1   3   0
3   2   0   2
3   3   2   0
3   3   3   1

• This is quite beautiful and surprising, thanks for your help! I hoped a 24 rook solution existed because it would make a good puzzle, so your answer is very satisfying! – Mike Earnest Jun 29 '15 at 5:24
• Do you have a reference for the result you quoted on the 3-dimensional version of the problem? – user48028 Jun 30 '15 at 19:08
• I found the problem and solution in Arthur Engel's Problem Solving Strategies, p. 44. – Mike Earnest Jun 30 '15 at 21:09

A dominating set of $(K_n)^{\square \,d}$ is equivalent to a $n$-ary covering code of length $d$ and covering radius $1$: just take the positions of the rooks to be the codewords. Known optimal sizes of covering codes are listed for example in Gerzson Kéri's website, although I don't know how up-to-date that information is.

The notation is such that $K_q(n,R)$ is the optimal size of a $q$-ary covering code of length $n$ and covering radius $R$. With the notation in this question, you are looking for $K_n(d,1)$. In particular, the answer for $(K_4)^{\square\,4}$ is $K_4(4,1)=24$, given in "Bounds for quaternary and quinary covering codes, listed for n <= 11, R <= 8 ".

(Yes, the $K_x$ part of the notation happens to be the same in both cases, which might be confusingly non-confusing; on the other hand the meaning of $n$ is different here and there.)