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

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

Offset: 1

Author

Andrey Zabolotskiy, Dec 11 2016

Keywords

• nonn
• hard
• more

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).

Examples

			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.
		

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.

Crossrefs

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

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).

Extensions

a(16)-a(22) from Andy Huchala, Mar 04 2024