cp's OEIS Frontend

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

%I A279402 #27 Mar 10 2024 07:54:48
%S A279402 1,1,1,2,3,3,4,4,5,5,5,6,7,7,5,8,9,8,10,10,7,11
%N A279402 Domination number for queen graph on an n X n toroidal board.
%C A279402 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 A279402 Row lengths of the triangle A279403.
%C A279402 All dominating sets are translation-invariant on the torus.
%C A279402 a(4*n) <= 2*n.
%C A279402 a(n) <= A075458(n).
%D A279402 John J. Watkins, Across the Board: The Mathematics of Chessboard Problem, Princeton University Press, 2004, pp. 139-140.
%H A279402 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 A279402 Andy Huchala, <a href="/A279402/a279402_1.py.txt">Python program</a>.
%H A279402 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 A279402 a(3*n) = n if n == 1, 5, 7, 11 (mod 12);
%F A279402 a(3*n) = n+1 if n == 2, 10 (mod 12);
%F A279402 a(3*n) = n+2 otherwise.
%F A279402 I.e., a(3*n) = 2*n - A085801(n).
%e A279402 The minimal dominating set for the queens' graph on a 15 X 15 toroidal board is:
%e A279402 ...............
%e A279402 ..........Q....
%e A279402 ...............
%e A279402 ...............
%e A279402 .Q.............
%e A279402 ...............
%e A279402 ...............
%e A279402 .......Q.......
%e A279402 ...............
%e A279402 ...............
%e A279402 .............Q.
%e A279402 ...............
%e A279402 ...............
%e A279402 ....Q..........
%e A279402 ...............
%e A279402 Hence a(15) = 5.
%Y A279402 Cf. A075458, A274138, A279403, A279404, A279405, A279406, A279407, A279408, A279409.
%K A279402 nonn,hard,more
%O A279402 1,4
%A A279402 _Andrey Zabolotskiy_, Dec 11 2016
%E A279402 a(16)-a(22) from _Andy Huchala_, Mar 04 2024