|
%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
|
