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

Table of n, a(n) for n=1..22.

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

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

Sequence in context: A070984 A134995 A194243 * A324475 A189705 A303601

Adjacent sequences: A279399 A279400 A279401 * A279403 A279404 A279405

Keyword

nonn,hard,more

Author

Andrey Zabolotskiy, Dec 11 2016

Extensions

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

Status

approved