6
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Jun 28 '15 at 23:49
  • $\begingroup$ 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. $\endgroup$ – Paul Burchett Jul 30 '15 at 15:06
5
$\begingroup$

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
$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Mike Earnest Jun 29 '15 at 5:24
  • $\begingroup$ Do you have a reference for the result you quoted on the 3-dimensional version of the problem? $\endgroup$ – user48028 Jun 30 '15 at 19:08
  • $\begingroup$ I found the problem and solution in Arthur Engel's Problem Solving Strategies, p. 44. $\endgroup$ – Mike Earnest Jun 30 '15 at 21:09
2
$\begingroup$

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

$\endgroup$

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.