A075324 -id:A075324 - cp's OEIS frontend

A075458 Domination number for queens' graph Q(n).

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

Offset: 1

N. J. A. Sloane, Oct 16 2002

From Dmitry Kamenetsky, Sep 03 2019: (Start)
Minimum number of queens needed to occupy or attack all squares of an n X n chessboard.
a(n) >= ceiling(n/2) for all n, except n = 3, 11. See paper by Finozhenok and Weakley below.
a(n) = p or p+1, where p = ceiling(n/2), proved for all n <= 132, except n = 3, 11. See paper by Ostergard and Weakley below. Note that this implies that a(n+4) > a(n). (End)

W. W. R. Ball and H. S. M. Coxeter, "Math'l Rec. and Essays," 13th Ed. Dover, p. 173.
John Watkins, Across the Board: The Mathematics of Chessboard Problems (2004), pp. 113-137

William Herbert Bird, Computational methods for domination problems, University of Victoria, 2017. See Table 5.1 on p. 114.
S. Bozóki, P. Gál, I. Marosi and W. D. Weakley, Domination of the rectangular queen's graph, arXiv:1606.02060 [math.CO], 2016.
Domingos M. Cardoso, Inês Serôdio Costa, and Rui Duarte, Spectral properties of the n-Queens' Graphs, arXiv:2012.01992 [math.CO], 2020. See p. 10.
Irene Choi, Shreyas Ekanathan, Aidan Gao, Tanya Khovanova, Sylvia Zia Lee, Rajarshi Mandal, Vaibhav Rastogi, Daniel Sheffield, Michael Yang, Angela Zhao, and Corey Zhao, The Struggles of Chessland, arXiv:2212.01468 [math.HO], 2022.
Dmitry Finozhenok and W. Doug Weakley, An Improved Lower Bound for Domination Numbers of the Queen’s Graph, Australasian Journal of Combinatorics, vol. 37, 2007, p. 295-300.
Dmitry Kamenetsky, Best known solutions for n <= 26.
Dmitry Kamenetsky, Matlab program to compute a(n) for small n.
Dmitry Kamenetsky, Java program to compute the best known solutions.
Matthew D. Kearse and Peter B. Gibbons, Computational Methods and New Results for Chessboard Problems, Australasian Journal of Combinatorics 23 (2001), 253-284.
Stephan Mertens, Domination Polynomial of the Rook Graph, arXiv:2401.00716 [math.CO], 2024.
Patric R. J. Östergård and William D. Weakley, Values of Domination Numbers of the Queen's Graph, The Electronic Journal of Combinatorics, volume 8, issue 1, 2001.
M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1926, p. 49.
A. Sinko and P. J. Slater, Queen's domination using border squares and (A,B)-restricted domination, Discrete Math., 308 (2008), 4822-4828.
Stan Wagon, Graph Theory Problems from Hexagonal and Traditional Chess, The College Mathematics Journal, Vol. 45, No. 4, September 2014, pp. 278-287.
Eric Weisstein's World of Mathematics, Domination Number
Eric Weisstein's World of Mathematics, Queen Graph
Eric Weisstein's World of Mathematics, Queens Problem

A002563 gives number of solutions.
Cf. A006075, A075561, A189889.
Cf. A075324 (independent domination number).

a(19) from Peter Karpov, Mar 01 2016

a(20)-a(24) from Bird and a(25) from Dmitry Kamenetsky's file added by Andrey Zabolotskiy, Sep 03 2021

A376732 Triangle read by rows: T(n,k) is the maximum number of squares covered (i.e., attacked) by k independent (i.e., non-attacking) queens on an n X n chessboard.

Original entry on oeis.org

1, 4, 0, 9, 9, 0, 12, 15, 16, 16, 17, 23, 25, 25, 25, 20, 30, 35, 36, 36, 36, 25, 37, 45, 49, 49, 49, 49, 28, 44, 55, 62, 64, 64, 64, 64, 33, 52, 66, 76, 81, 81, 81, 81, 81, 36, 60, 77, 92, 100, 100, 100, 100, 100, 100, 41, 68, 88, 104, 121, 121, 121, 121, 121, 121, 121

Offset: 1

John King, Oct 03 2024

T(2,2) = T(3,3) = 0 indicate that there are no solutions to the n-queens problem when n is 2 or 3.

			Triangle begins:
  n\k|  1    2    3    4    5    6    7    8    9   10   11   12
 ----+-----------------------------------------------------------
   1 |  1;
   2 |  4,   0;
   3 |  9,   9,   0;
   4 | 12,  15,  16,  16;
   5 | 17,  23,  25,  25,  25;
   6 | 20,  30,  35,  36,  36,  36;
   7 | 25,  37,  45,  49,  49,  49,  49;
   8 | 28,  44,  55,  62,  64,  64,  64,  64;
   9 | 33,  52,  66,  76,  81,  81,  81,  81,  81;
  10 | 36,  60,  77,  92, 100, 100, 100, 100, 100, 100;
  11 | 41,  68,  88, 104, 121, 121, 121, 121, 121, 121, 121;
  12 | 44,  76, 101, 120, 134, 142, 144, 144, 144, 144, 144, 144;
  13 | 49,  84, 112, 136, 153, 165, 169, 169, 169, 169, 169, ...;
  14 | 52,  92, 125, 152, 172, 186, 194, 196, 196, 196, 196, ...;
  15 | 57, 100, 136, 168, 193, 209, 221, 224, 225, 225, 225, ...;
  16 | 60, 108, 149, 184, 212, 231, 242, 251, 256, 256, 256, ...;
  17 | 65, 116, 160, 200, 233, 255, 269, 281, 289, 289, 289, ...;
  18 | 68, 124, 173, 216, 252, 277, 294, 310, 322, 324, 324, ...;
  ...

Mia Muessig, Table of n, a(n) for n = 1..240
John King, Examples for Queens 1,2,3,4,5 up to 11x11.
John King, Examples for Queens 6,7,8,9 up to 15x15.
Mia Muessig, Julia code to compute the sequence

Columns 1..8 are A047461, A374933, A375116, A374934, A374935, A374936, A374937, A374938.

Cf. A075324, A002567, A075458, A274947.

T(n,k) = n^2 for k >= A075324(n), n >= 4.

Initial terms by John King and Mia Müßig added by Mia Muessig, Oct 05 2024

A279404 Independent domination number for queens' graph on an n X n toroidal board.

Original entry on oeis.org

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

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, but not both.

A279402(n) <= a(n) <= A085801(n).

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. A075324, A085801, A279402.

a(3*n) = n if n = 1, 5, 7, 11 (mod 12).

a(17)-a(18) from Andy Huchala, Mar 09 2024

A002567 Number of nonisomorphic solutions to minimal independent dominating set on queens' graph Q(n).

Original entry on oeis.org

1, 1, 1, 2, 2, 17, 1, 91, 16, 1, 1, 105, 4, 55, 1314, 16, 2, 28

Offset: 1

N. J. A. Sloane

W. Ahrens, Mathematische Unterhaltungen und Spiele, second edition (1910), Vol. 1, p. 301.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

P. B. Gibbons and J. A. Webb, Some new results for the queens domination problem, Australasian Journal of Combinatorics 15 (1997), pp. 145-160.
Matthew D. Kearse and Peter B. Gibbons, Computational Methods and New Results for Chessboard Problems, Australasian Journal of Combinatorics 23 (2001), 253-284.
M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1923, 64 pages. See p. 49.
M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1923, 64 pages. See p. 49. [Incomplete annotated scan of title page and pages 18-51]

See A002568 for the number of distinct solutions.

A075324 gives number of queens required.

a(9) corrected by Peter Gibbons, May 30 2004

A374935 Maximum number of squares covered (i.e., attacked) by 5 independent (i.e., nonattacking) queens on an n X n chessboard.

Original entry on oeis.org

25, 36, 49, 64, 81, 100, 121, 134, 153, 172, 193, 212, 233, 252

Offset: 5

John King, Aug 08 2024

			5 X 5; 6 X 6; 7 X 7; 8 X 8;  Center-square +4Queens separated as if 1,2 knights.
              at 11 X 11 and beyond this pattern seems to be 'best'.
  x x x x x x x x
  x x x x x x x x
  x x Q x x x x x
  x x x x x Q x x
  x x x Q x x x x
  x Q x x x x x x
  x x x x Q x x x
  x x x x x x x x
9 X 9; 10 X 10; 11 X 11; Center-square +4Queens separated as 2,4 knights.
  x x x x x x x x x x x
  x x x x x x x Q x x x
  x x x x x x x x x x x
  x Q x x x x x x x x x
  x x x x x x x x x x x
  x x x x x Q x x x x x
  x x x x x x x x x x x
  x x x x x x x x x Q x
  x x x x x x x x x x x
  x x x Q x x x x x x x
  x x x x x x x x x x x

Column 5 of A376732.

Cf. A075324, A047461, A374933, A375116, A374933, A374934, A374936.

Unverified a(19) removed by Andrew Howroyd, Oct 05 2024

A374936 Maximum number of squares covered (i.e., attacked) by 6 independent (i.e., nonattacking) queens on an n X n chessboard.

Original entry on oeis.org

36, 49, 64, 81, 100, 121, 142, 165, 186, 209, 231, 255, 277

Offset: 6

John King, Aug 08 2024

			Example for 12 X 12: There are 2 cells marked 'o' or uncovered thus a(12) = 12 * 12 - 2 = 142.
  x x x x x x x x x x x Q
  x x x x x x x x x x x x
  x x x x x x x x x x x x
  x x x Q x x x x x x x x
  x x x x x Q x x x x x x
  x x x x x x x Q x x x x
  x x x x Q x x x x x x x
  x x x x x x Q x x x x x
  o x x x x x x x x x x x
  x x x x x x x x x x x x
  x x x x x x x x x x x x
  x x x x x x x x o x x x
From _Christian Sievers_, Sep 08 2024: (Start)
Example for 14 X 14 with 186 attacked squares (unattacked ones marked with "+"):
  . . Q . . . . . . . . . . .
  . . . . . . . . . Q . . . .
  . . . . . . . . . . . . . +
  . + . . . . . . . . . . . .
  . . . Q . . . . . . . . . .
  . . . . . . . . . . . . . .
  . . . . . . . . . . . . . .
  . . . . . . . . . . . . Q .
  . + . . . . . . . . . . . .
  . . . . . . . . . . . . . +
  . . . . . . Q . . . . . . .
  . + . . + . . . . . . + . .
  . . . . . + . . . . + . . +
  Q . . . . . . . . . . . . .
(End)

Column 6 of A376732.

Cf. A075324, A047461, A374933, A375116, A374933, A374934, A374935, A374937, A374938.

a(14) corrected and a(15) confirmed by Christian Sievers, Sep 08 2024

a(16)-a(18) added using data from Mia Muessig by Andrew Howroyd, Oct 05 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

A229803 Domination number for rook graph HR(n) on a triangular board of hexagonal cells. The rook can move along any row of adjacent cells, in any of the three directions.

Original entry on oeis.org

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

Offset: 1

Stan Wagon, Sep 29 2013

The value for HR(20) was obtained by Rob Pratt, Sep 29 2013, using integer-linear programming.

			For HR(7), the graph can be dominated by the three vertices 6, 11, 26, where we count down from the top.
This graph was called the Queen graph in the DeMaio and Tran paper, but the moves are those of a rook in the classic hexagonal chess game.

J. Konhauser, D. Velleman, S. Wagon, Which Way Did the Bicycle Go? Washington, DC, Math. Assoc. of America, 1996, pp. 169-172

William Herbert Bird, Computational methods for domination problems, University of Victoria, 2017. See Table 2.4 on p. 32.
J. DeMaio and H. L. Tran, Domination and independence on a triangular honeycomb chessboard, Coll. Math. J. 44 (2013) 307-314.
Stan Wagon, Graph Theory Problems from Hexagonal and Traditional Chess, The College Mathematics Journal, Vol. 45, No. 4, September 2014, pp. 278-287

Cf. A075458, A075324, A075561, A006075.

a(21)-a(24) from Bird added by Andrey Zabolotskiy, Sep 03 2021

cp's OEIS Frontend

A075458 Domination number for queens' graph Q(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A376732 Triangle read by rows: T(n,k) is the maximum number of squares covered (i.e., attacked) by k independent (i.e., non-attacking) queens on an n X n chessboard.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A279404 Independent domination number for queens' graph on an n X n toroidal board.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A002567 Number of nonisomorphic solutions to minimal independent dominating set on queens' graph Q(n).

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A374935 Maximum number of squares covered (i.e., attacked) by 5 independent (i.e., nonattacking) queens on an n X n chessboard.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A374936 Maximum number of squares covered (i.e., attacked) by 6 independent (i.e., nonattacking) queens on an n X n chessboard.

Views

Author

Keywords

Examples

Crossrefs

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

A229803 Domination number for rook graph HR(n) on a triangular board of hexagonal cells. The rook can move along any row of adjacent cells, in any of the three directions.