OFFSET
1,4
COMMENTS
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.
Row lengths of the triangle A279403.
All dominating sets are translation-invariant on the torus.
a(4*n) <= 2*n.
a(n) <= A075458(n).
REFERENCES
John J. Watkins, Across the Board: The Mathematics of Chessboard Problem, Princeton University Press, 2004, pp. 139-140.
LINKS
A. P. Burger and C. M. Mynhardt, The domination number of the toroidal queens graph of size 3k × 3k, Australasian Journal of Combinatorics, 28 (2003), 137-148.
Andy Huchala, Python program.
Christina M. Mynhardt, Upper bounds for the domination numbers of toroidal queens graphs, Discussiones Mathematicae Graph Theory, 23 (2003), 163-175.
FORMULA
a(3*n) = n if n == 1, 5, 7, 11 (mod 12);
a(3*n) = n+1 if n == 2, 10 (mod 12);
a(3*n) = n+2 otherwise.
I.e., a(3*n) = 2*n - A085801(n).
EXAMPLE
The minimal dominating set for the queens' graph on a 15 X 15 toroidal board is:
...............
..........Q....
...............
...............
.Q.............
...............
...............
.......Q.......
...............
...............
.............Q.
...............
...............
....Q..........
...............
Hence a(15) = 5.
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Andrey Zabolotskiy, Dec 11 2016
EXTENSIONS
a(16)-a(22) from Andy Huchala, Mar 04 2024
STATUS
approved