A279407 -id:A279407 - cp's OEIS frontend

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

Andrey Zabolotskiy, Dec 11 2016

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

			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.

John J. Watkins, Across the Board: The Mathematics of Chessboard Problem, Princeton University Press, 2004, pp. 139-140.

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.

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

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

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

A279408 Triangle read by rows: T(n,m) (n>=m>=1) = domination number for kings' graph on an n X m toroidal board.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 2, 2, 2, 4, 4, 2, 2, 2, 4, 4, 4, 3, 3, 3, 5, 5, 6, 7, 3, 3, 3, 6, 6, 6, 8, 8, 3, 3, 3, 6, 6, 6, 9, 9, 9, 4, 4, 4, 7, 7, 8, 10, 11, 12, 14, 4, 4, 4, 8, 8, 8, 11, 11, 12, 15, 15, 4, 4, 4, 8, 8, 8, 12, 12, 12, 16, 16, 16, 5, 5, 5, 9, 9, 10, 13, 14, 15, 18, 19, 20, 22

Offset: 1

Andrey Zabolotskiy, Dec 16 2016

That is, the minimal number of kings needed to cover an n X m toroidal chessboard so that every square has a king on it, is under attack by a king, or both.

For the usual non-toroidal case, the formula is ceiling(m/3)*ceiling(n/3).

			T(7,7)=7 can be reached by:
...K...
......K
..K....
.....K.
.K.....
....K..
K......

John J. Watkins, Across the Board: The Mathematics of Chessboard Problem, Princeton University Press, 2004, pages 144-149.

Indranil Ghosh, Rows 1..100, flattened
Dan Freeman, Chessboard Puzzles Part 4 - Other Surfaces and Variations.

Cf. A075561, A279402, A279407, A279209.

Flatten[Table[Ceiling[Max[m Ceiling[n/3], n Ceiling[m/3]]/3],{n, 1, 13}, {m, 1, n}]] (* Indranil Ghosh, Mar 09 2017 *)

T(n,m) = ceil(max(m*ceil(n/3), n*ceil(m/3))/3)
for(n=1,20,for(m=1,n, print1(T(n,m)", "))) \\ Charles R Greathouse IV, Dec 16 2016

T(n,m) = ceiling(max(m*ceiling(n/3), n*ceiling(m/3))/3).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions