login
Domination number for queen graph on an n X n toroidal board.
6

%I #27 Mar 10 2024 07:54:48

%S 1,1,1,2,3,3,4,4,5,5,5,6,7,7,5,8,9,8,10,10,7,11

%N Domination number for queen graph on an n X n toroidal board.

%C That is, the minimal number of queens needed to cover an n X n toroidal chessboard so that every square either has a queen on it, or is under attack by a queen, or both.

%C Row lengths of the triangle A279403.

%C All dominating sets are translation-invariant on the torus.

%C a(4*n) <= 2*n.

%C a(n) <= A075458(n).

%D John J. Watkins, Across the Board: The Mathematics of Chessboard Problem, Princeton University Press, 2004, pp. 139-140.

%H A. P. Burger and C. M. Mynhardt, <a href="https://ajc.maths.uq.edu.au/pdf/28/ajc_v28_p137.pdf">The domination number of the toroidal queens graph of size 3k × 3k</a>, Australasian Journal of Combinatorics, 28 (2003), 137-148.

%H Andy Huchala, <a href="/A279402/a279402_1.py.txt">Python program</a>.

%H Christina M. Mynhardt, <a href="https://doi.org/10.7151/dmgt.1193">Upper bounds for the domination numbers of toroidal queens graphs</a>, Discussiones Mathematicae Graph Theory, 23 (2003), 163-175.

%F a(3*n) = n if n == 1, 5, 7, 11 (mod 12);

%F a(3*n) = n+1 if n == 2, 10 (mod 12);

%F a(3*n) = n+2 otherwise.

%F I.e., a(3*n) = 2*n - A085801(n).

%e The minimal dominating set for the queens' graph on a 15 X 15 toroidal board is:

%e ...............

%e ..........Q....

%e ...............

%e ...............

%e .Q.............

%e ...............

%e ...............

%e .......Q.......

%e ...............

%e ...............

%e .............Q.

%e ...............

%e ...............

%e ....Q..........

%e ...............

%e Hence a(15) = 5.

%Y Cf. A075458, A274138, A279403, A279404, A279405, A279406, A279407, A279408, A279409.

%K nonn,hard,more

%O 1,4

%A _Andrey Zabolotskiy_, Dec 11 2016

%E a(16)-a(22) from _Andy Huchala_, Mar 04 2024