A279404 -id:A279404 - cp's OEIS frontend

A085801 Maximum number of nonattacking queens on an n X n toroidal board.

1, 1, 1, 2, 5, 4, 7, 6, 7, 9, 11, 10, 13, 13, 13, 14, 17, 16, 19, 18, 19, 21, 23, 22, 25, 25, 25, 26, 29, 28, 31, 30, 31, 33, 35, 34, 37, 37, 37, 38, 41, 40, 43, 42, 43, 45, 47, 46, 49, 49, 49, 50, 53, 52, 55, 54, 55, 57, 59, 58, 61, 61, 61, 62, 65, 64, 67, 66

Offset: 1

Konrad Schlude, Jul 24 2003

Independence number of the queens' graph on toroidal n X n board. - Andrey Zabolotskiy, Dec 11 2016

			Four non-attacking queens can be placed on a 6 X 6 toroidal board:
......
..Q...
....Q.
.Q....
...Q..
......
But five queens cannot. Hence a(6) = 4.

G. Polya: Über die 'Doppelt-Periodischen' Loesungen des n-Damen-Problems, in: W. Ahrens: Mathematische Unterhaltungen und Spiele, Teubner, Leipzig, 1918, 364-374. Reprinted in: G. Polya: Collected Works, Vol. V, 237-247.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Grant Cairns, Queens on Non-square Tori, El. J. Combinatorics, N6, 2001
Eldar Fischer, Tomer Kotek, and Johann A. Makowsky, Application of Logic to Combinatorial Sequences and Their Recurrence Relations
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 751.
P. Monsky, Problem E3162, Amer. Math. Monthly 96 (1989), 258-259.
Konrad Schlude and Ernst Specker, Zum Problem der Damen auf dem Torus, Technical Report 412, Computer Science Department ETH Zurich, 2003.

Cf. A051906, A007705, A279402, A279404, A279405, A172517, A172518, A172519, A173775, A178722.

(* Explicit formula, based on an article by Monsky: *)
Table[n-1/6*(2*Cos[Pi*n/2]-3*Cos[Pi*n/3]+5*Cos[2*Pi*n/3]-Cos[Pi*n/6]-Cos[5*Pi*n/6]+3*Cos[Pi*n]+7),{n,1,100}] (* Vaclav Kotesovec, Dec 13 2010 *)

a(n)=n-1/6*(2*cos(Pi*n/2)-3*cos(Pi*n/3)+5*cos(2*Pi*n/3)-cos(Pi*n/6)-cos(5*Pi*n/6)+3*cos(Pi*n)+7);
vector(60,n,round(a(n))) \\ Joerg Arndt, Dec 13 2010

G.f.: (2*x^12 - x^11 + 2*x^10 + 2*x^9 + x^8 - x^7 + 3*x^6 - x^5 + 3*x^4 + x^3 + 1)/(x^13 - x^12 - x + 1) = (2*x^12 - x^11 + 2*x^10 + 2*x^9 + x^8 - x^7 + 3*x^6 - x^5 + 3*x^4 + x^3 + 1)/((x - 1)^2*(x + 1)*(x^2 + 1)*(x^2 - x + 1)*(x^2 + x + 1)*(x^4 - x^2 + 1)). - Joerg Arndt, Dec 13 2010
From Andrey Zabolotskiy, Dec 11 2016: (Start)
a(n) = n if n = 1, 5, 7, 11 (mod 12);
a(n) = n-1 if n = 2, 10 (mod 12);
a(n) = n-2 otherwise.
(End)

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

Original entry on oeis.org

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

A299029 Triangle read by rows: Independent domination number for rectangular queens graph Q(n,m), 1 <= n <= m.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 1, 2, 2, 3, 3, 1, 2, 2, 3, 3, 4, 1, 2, 3, 3, 4, 4, 4, 1, 2, 3, 4, 4, 4, 5, 5, 1, 2, 3, 4, 4, 4, 5, 5, 5, 1, 2, 3, 4, 4, 4, 5, 5, 5, 5, 1, 2, 3, 4, 4, 5, 5, 6, 5, 5, 5, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 7, 7, 7, 1, 2, 3, 4, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8

Offset: 1

Sandor Bozoki, Feb 01 2018

The queens graph Q(n X m) has the squares of the n X m chessboard as its vertices; two squares are adjacent if they are both in the same row, column, or diagonal of the board. A set D of squares of Q(n X m) is a dominating set for Q(n X m) if every square of Q(n X m) is either in D or adjacent to a square in D. The minimum size of an independent dominating set of Q(n X m) is the independent domination number, denoted by i(Q(n X m)).
Less formally, i(Q(n X m)) is the number of independent queens that are necessary and sufficient to all squares of the n X m chessboard be occupied or attacked.
Chessboards 8 X 11 and 18 X 11 are of special interest, because they cannot be dominated by 5 and 8 independent queens, respectively, although the larger boards 9 X 11, 10 X 11, 11 X 11 and 18 X 12 are. It is open how many such counterexamples of this kind of monotonicity exist.

			Table begins
  m\n| 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18
  ---+-----------------------------------------------------
   1 | 1
   2 | 1  1
   3 | 1  1  1
   4 | 1  2  2  3
   5 | 1  2  2  3  3
   6 | 1  2  2  3  3  4
   7 | 1  2  3  3  4  4  4
   8 | 1  2  3  4  4  4  5  5
   9 | 1  2  3  4  4  4  5  5  5
  10 | 1  2  3  4  4  4  5  5  5  5
  11 | 1  2  3  4  4  5  5  6  5  5  5
  12 | 1  2  3  4  4  5  5  6  6  6  6  7
  13 | 1  2  3  4  5  5  6  6  6  7  7  7  7
  14 | 1  2  3  4  5  6  6  6  6  7  7  8  8  8
  15 | 1  2  3  4  5  6  6  7  7  7  7  8  8  9  9
  16 | 1  2  3  4  5  6  6  7  7  7  8  8  8  9  9  9
  17 | 1  2  3  4  5  6  7  7  7  8  8  8  9  9  9  9  9
  18 | 1  2  3  4  5  6  7  7  8  8  9  8  9  9  9 10 10 10

Sandor Bozoki, First 18 rows of the triangle, formatted as a simple linear sequence n, a(n) for n = 1..171
S. Bozóki, P. Gál, I. Marosi, W. D. Weakley, Domination of the rectangular queens graph, arXiv:1606.02060 [math.CO], 2016.
S. Bozóki, P. Gál, I. Marosi, W. D. Weakley, Domination of the rectangular queens graph, 2016.
Eric Weisstein's World of Mathematics, Queen Graph
Eric Weisstein's World of Mathematics, Queens Problem

Diagonal elements are in A075324: Independent domination number for queens graph Q(n).
Cf. A274138: Domination number for rectangular queens graph Q(n,m).
Cf. A279404: Independent domination number for queens graph on an n X n toroidal board.

A321684 Independent domination number of the n X n grid graph.

Original entry on oeis.org

0, 1, 2, 3, 4, 7, 10, 12, 16, 21, 24, 30, 35, 40, 47, 53, 60, 68, 76, 84, 92, 101, 111, 121, 131, 141, 152, 164, 176, 188, 200, 213, 227, 241, 255, 269, 284, 300, 316, 332, 348, 365, 383, 401, 419, 437, 456, 476, 496, 516, 536, 557, 579, 601, 623, 645, 668

Offset: 0

Andrey Zabolotskiy, Jan 14 2019

Colin Barker, Table of n, a(n) for n = 0..1000
Simon Crevals, Patric R. J. Östergård, Independent domination of grids, Discrete Math., 338 (2015), 1379-1384.
Index entries for linear recurrences with constant coefficients, signature (2,-1,0,0,1,-2,1).

Cf. A104519, A075324, A299029, A279404, A291297.

ogf := (-41*x^6 + 47*x^5 - x^3 - x^2 + 41*x - 47)/((x - 1)^3*(x^4 + x^3 + x^2 + x + 1)): ser := series(ogf, x, 44):
(0,1,2,3,4,7,10,12,16,21,24,30,35,40), seq(coeff(ser, x, n), n=0..42); # Peter Luschny, Jan 14 2019

concat(0, Vec(x*(1 + 2*x^4 - x^5 - x^6 + 2*x^7 + x^8 - 4*x^9 + 3*x^10 - 2*x^12 + x^13 + x^14 - 2*x^15 + 2*x^16 - 2*x^18 + x^19) / ((1 - x)^3*(1 + x + x^2 + x^3 + x^4)) + O(x^40))) \\ Colin Barker, Jan 14 2019

For n >= 14, a(n) = floor((n+2)^2 / 5 - 4).
a(n) = A104519(n+2), the domination number of the n X n grid graph, for all n except for n = 9, 11.
From Colin Barker, Jan 14 2019: (Start)
G.f.: x*(1 + 2*x^4 - x^5 - x^6 + 2*x^7 + x^8 - 4*x^9 + 3*x^10 - 2*x^12 + x^13 + x^14 - 2*x^15 + 2*x^16 - 2*x^18 + x^19) / ((1 - x)^3*(1 + x + x^2 + x^3 + x^4)).
a(n) = 2*a(n-1) - a(n-2) + a(n-5) - 2*a(n-6) + a(n-7) for n > 20.
(End)

A342576 Independent domination number for knight graph on an n X n board.

Original entry on oeis.org

1, 4, 4, 4, 5, 8, 13, 14, 14, 16, 22, 24, 29, 33, 36, 40, 47, 52, 58, 63, 68

Offset: 1

Andrey Zabolotskiy, Mar 15 2021

Sandra M. Hedetniemi, Stephen T. Hedetniemi, Robert Reynolds, Combinatorial Problems on Chessboards: II, in: Domination in Graphs - Advanced Topics, Marcel Dekker, 1998. See p. 141.

Andy Huchala, Python program.
Robert Israel, Optimal configurations for n = 3 to 14
Eric Weisstein's World of Mathematics, Knight Graph.
Eric Weisstein's World of Mathematics, Lower Independence Number.

Cf. A006075, A075324, A299029, A279404, A030978.

f:= proc(N)
  local verts,Rverts,edg,cons,i,j,e;
  verts:= [seq(seq([i,j],i=1..N),j=1..N)]:
  for i from 1 to N^2 do Rverts[op(verts[i])]:= i od:
  edg:= {seq(seq({Rverts[i,j],Rverts[i+1,j+2]},i=1..N-1),j=1..N-2),
       seq(seq({Rverts[i,j],Rverts[i+2,j+1]},i=1..N-2),j=1..N-1),
       seq(seq({Rverts[i,j],Rverts[i+1,j-2]},i=1..N-1),j=3..N),
       seq(seq({Rverts[i,j],Rverts[i+2,j-1]},i=1..N-2),j=2..N)}:
  cons:= {seq(x[e[1]]+x[e[2]]<=1, e=edg),
    seq(x[i]+add(`if`(member({i,j},edg),x[j],0),j=1..N^2)>=1, i=1..N^2)}:
  Optimization:-Minimize(add(x[i],i=1..N^2),cons,assume=binary)[1]
end proc:
map(f, [$1..13]); # Robert Israel, Mar 17 2021

a(11) to a(14) from Robert Israel, Mar 17 2021
a(15)-a(18) from Eric W. Weisstein, Aug 01 2023
a(19) from Eric W. Weisstein, Jan 14 2024
a(20)-a(21) from Andy Huchala, Mar 10 2024

cp's OEIS Frontend

A085801 Maximum number of nonattacking queens on an n X n toroidal board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A299029 Triangle read by rows: Independent domination number for rectangular queens graph Q(n,m), 1 <= n <= m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A321684 Independent domination number of the n X n grid graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A342576 Independent domination number for knight graph on an n X n board.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Extensions