

A279402


Domination number for queens' graph on an n X n toroidal board.


5



1, 1, 1, 2, 3, 3, 4, 4, 5, 5, 5, 6, 7, 7, 5
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 translationinvariant 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, pages 139140.


LINKS

Table of n, a(n) for n=1..15.
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), 137148.
Christina M. Mynhardt, Upper bounds for the domination numbers of toroidal queens graphs, Discussiones Mathematicae Graph Theory, 23 (2003), 163175, DOI:10.7151/dmgt.1193.


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

Cf. A075458, A274138, A279403A279409.
Sequence in context: A070984 A134995 A194243 * A189705 A303601 A031247
Adjacent sequences: A279399 A279400 A279401 * A279403 A279404 A279405


KEYWORD

nonn,hard,more


AUTHOR

Andrey Zabolotskiy, Dec 11 2016


STATUS

approved



