A075458 -id:A075458 - cp's OEIS frontend

A140858 This sequence is identical with A075458.

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

Offset: 1

dead

A075561 Domination number for kings' graph K(n).

1, 1, 1, 4, 4, 4, 9, 9, 9, 16, 16, 16, 25, 25, 25, 36, 36, 36, 49, 49, 49, 64, 64, 64, 81, 81, 81, 100, 100, 100, 121, 121, 121, 144, 144, 144, 169, 169, 169, 196, 196, 196, 225, 225, 225, 256, 256, 256, 289, 289, 289, 324, 324, 324, 361, 361, 361, 400, 400

Offset: 1

N. J. A. Sloane, Oct 16 2002

Also the lower independence number of the n X n knight graph. - Eric W. Weisstein, Aug 01 2023

John J. Watkins, Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, 2004, p. 102.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
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.
Matthew D. Kearse and Peter B. Gibbons, Computational Methods and New Results for Chessboard Problems, Centre for Discrete Mathematics and Theoretical Computer Science, CDMTCS-133, May 2000.
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 Polynomials of the Grid, the Cylinder, the Torus, and the King Graph, arXiv:2408.08053 [math.CO], 2024. See p. 15.
Eric Weisstein's World of Mathematics, Domination Number
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Kings Problem
Eric Weisstein's World of Mathematics, Lower Independence Number
Index entries for linear recurrences with constant coefficients, signature (1,0,2,-2,0,-1,1).

Cf. A189889, A075458, A006075, A102753.

Table[Floor[(n + 2)/3]^2, {n, 50}] (* Vaclav Kotesovec, May 13 2012 *)
LinearRecurrence[{1, 0, 2, -2, 0, -1, 1}, {1, 1, 1, 4, 4, 4, 9}, 20] (* Eric W. Weisstein, Jun 20 2017 *)
CoefficientList[Series[(-1 - x^3)/((-1 + x)^3 (1 + x + x^2)^2), {x, 0, 20}], x] (* Eric W. Weisstein, Jun 20 2017 *)

Vec(-x*(x+1)*(x^2-x+1)/((x-1)^3*(x^2+x+1)^2) + O(x^100)) \\ Colin Barker, Oct 06 2014

a(n) = floor((n+2)/3)^2. - Vaclav Kotesovec, May 13 2012
G.f.: -x*(x+1)*(x^2-x+1) / ((x-1)^3*(x^2+x+1)^2). - Colin Barker, Oct 06 2014
E.g.f.: exp(-x/2)*(exp(3*x/2)*(5 + 3*x*(3 + x)) + (6*x - 5)*cos(sqrt(3)*x/2) + sqrt(3)*(3 + 2*x)*sin(sqrt(3)*x/2))/27. - Stefano Spezia, Oct 17 2022
Sum_{n>=1} 1/a(n) = Pi^2/2 (A102753). - Amiram Eldar, Nov 03 2022

More terms added from Vaclav Kotesovec, May 13 2012

A006075 Minimal number of knights needed to cover an n X n board.

Original entry on oeis.org

1, 4, 4, 4, 5, 8, 10, 12, 14, 16, 21, 24, 28, 32, 36, 40, 46, 52, 57, 62, 68

Offset: 1

N. J. A. Sloane

How many knights are needed to occupy or attack every square of an n X n board?
Also known as the domination number of the n X n knight graph. - Eric W. Weisstein, May 27 2016
Upper bounds for the terms after a(20) = 62 are as follows: 68, 75, 82, 88, 96, 102, ... (see Frank Rubin's web site).
The value a(15) = 37 given by Jackson and Pargas is wrong. A simulated annealing-based program I wrote found several complete coverages of a 15 X 15 board with 36 knights. - John Danaher (jsd(AT)mit.edu), Oct 24 2000

			Illustrations for a(3) = 4, a(4) = 4, a(5) = 5 (o = empty square, X = knight):
ooo .. oooo .. ooooo
oXo .. oXXo .. ooXoo
XXX .. oXXo .. oXXXo
...... oooo .. ooXoo
.............. ooooo

David C. Fisher, On the N X N Knight Cover Problem, Ars Combinatoria 69 (2003), 255-274.
M. Gardner, Mathematical Magic Show. Random House, NY, 1978, p. 194.
Anderson H. Jackson and Roy P. Pargas, Solutions to the N x N Knights Cover Problem, J. Recreat. Math., Vol. 23(4), 1991, 255-267.
Bernard Lemaire, Knights Covers on N X N Chessboards, J. Recreat. Math., Vol. 31-2, 2003, 87-99.
Frank Rubin, Improved knight coverings, Ars Combinatoria 69 (2003), 185-196.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
John Watkins, Across the Board: The Mathematics of Chessboard Problems (2004), p. 97.

J. Danaher, Results for 15 X 15 board.
Andy Huchala, Python program.
Lee Morgenstern, Knight Domination. [Much material, including optimality proofs for the values given in this entry]
Frank Rubin, Contest Center Web Site, Knight Coverings for Large Chessboards. [Much material, including many illustrations]
Frank Rubin, Illustration of three 52-knight coverings of an 18 X 18 board. (see Frank Rubin's web site, from which this is taken, for many further examples)
Eric Weisstein's World of Mathematics, Domination Number.
Eric Weisstein's World of Mathematics, Knight Graph.
Eric Weisstein's World of Mathematics, Knights Problem.

A006076 gives number of inequivalent ways to cover the board using a(n) knights, A103315 gives total number.

Cf. A075458, A075561, A189889, A342576.

Terms (or bounds) through a(26) updated by Frank Rubin (contestcen(AT)aol.com), May 22 2002
a(20) added from the Contest Center web site by N. J. A. Sloane, Mar 02 2006
a(21) added by Andy Huchala, Jun 06 2021

A075324 Independent domination number for queens' graph Q(n).

Original entry on oeis.org

1, 1, 1, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 8, 9, 9, 9, 10, 11, 11, 11, 12, 13, 13, 13, 14, 15, 15, 16, 16, 17

Offset: 1

N. J. A. Sloane, Oct 16 2002

			a(8) = 5 queens attacking all squares of standard chessboard:
  . . . . . . . .
  . . . . . Q . .
  . . Q . . . . .
  . . . . Q . . .
  . . . . . . Q .
  . . . Q . . . .
  . . . . . . . .
  . . . . . . . .

W. W. R. Ball and H. S. M. Coxeter, Math'l Rec. and Essays, 13th Ed. Dover, p. 173.
C. Berge, Graphs and Hypergraphs, North-Holland, 1973; p. 304, Example 2.
M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1926, p. 49.

William Herbert Bird, Computational methods for domination problems, University of Victoria, 2017. See Table 5.1 on p. 114.
Matthew D. Kearse and Peter B. Gibbons, Computational Methods and New Results for Chessboard Problems, Australasian Journal of Combinatorics 23 (2001), 253-284.
Alexis Langlois-Rémillard, Christoph Müßig, and Érika Róldan, Complexity of Chess Domination Problems, arXiv:2211.05651 [math.CO], 2022.
Alexis Langlois-Rémillard, Christoph Müßig, and Érika Róldan, Solution a(26)-a(31) and Julia code to compute the sequence, 2022.

A002567 gives the number of solutions.

Cf. A075458 (not necessarily independent).

a(19)-a(24) from Bird and a(25) from Kearse & Gibbons added by Andrey Zabolotskiy, Sep 03 2021
a(26) from Alexis Langlois-Rémillard, Christoph Müßig and Érika Roldán added by Christoph Muessig, Aug 25 2022
a(27)-a(31) from Alexis Langlois-Rémillard, Christoph Müßig and Érika Roldán added by Christoph Muessig, Sep 19 2022

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

A002564 Number of different ways one can attack all squares on an n X n chessboard using the minimum number of queens.

Original entry on oeis.org

1, 4, 1, 12, 186, 4, 86, 4860, 114, 8, 2, 8, 288, 4632, 205832, 2968, 124, 16, 84

Offset: 1

N. J. A. Sloane

Number of distinct solutions to minimum dominating set on queens' graph Q(n). See A002563 for non-isomorphic solutions.
For same problem, but with non-attacking queens, see A002568. - Vaclav Kotesovec, Sep 07 2012
In other words, number of minimum dominating sets in the n X n queen graph. - Eric W. Weisstein, Dec 31 2017
For n > 2, also the number of minimal edge covers in the n X n queen graph. - Eric W. Weisstein, Dec 09 2024
a(20) >= 4152. - Eric W. Weisstein, Jul 28 2025

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

Andy Huchala, Python program.
Matthew D. Kearse and Peter B. Gibbons, Computational Methods and New Results for Chessboard Problems, Australasian Journal of Combinatorics 23 (2001), 253-284.
Mia Müßig, Julia code to compute the sequence
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]
Eric Weisstein's World of Mathematics, Minimal Edge Cover.
Eric Weisstein's World of Mathematics, Minimum Dominating Set.
Eric Weisstein's World of Mathematics, Queen Graph.
Eric W. Weisstein, Symmetrically inequivalent configurations for n = 1 to 7
Eric W. Weisstein, Symmetrically inequivalent configurations for n = 8
Eric W. Weisstein, Symmetrically inequivalent configurations for n = 9 to 13
Eric W. Weisstein, Symmetrically inequivalent configurations for n = 14
Eric W. Weisstein, Symmetrically inequivalent configurations for n = 16
Eric W. Weisstein, Symmetrically inequivalent configurations for n = 17 to 19

Cf. A002563, A002568, A182333, A286883.

A075458 gives number of queens required. - Sean A. Irvine, Apr 05 2014

New name of the sequence from Vaclav Kotesovec, Sep 07 2012
a(9)-a(10) from Vaclav Kotesovec, Sep 07 2012
a(11) from Svyatoslav Starkov, Sep 16 2013
a(12)-a(13) from Sean A. Irvine, Apr 07 2014
Definition edited by N. J. A. Sloane, Dec 25 2017 at the suggestion of Brendan McKay.
a(14) from Andy Huchala, Mar 13 2024
a(15)-a(19) from Mia Muessig, Oct 04 2024

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

A274947 Irregular triangle read by rows: T(n,k) (n>=0, 0 <= k <= n^2) = least number of squares attacked by k queens on an n X n board.

Original entry on oeis.org

0, 0, 1, 0, 4, 4, 4, 4, 0, 7, 8, 9, 9, 9, 9, 9, 9, 9, 0, 10, 13, 14, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 0, 13, 18, 20, 21, 22, 23, 23, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 0, 16, 23, 27, 28, 30, 31, 32, 32, 33, 34, 34, 34, 34, 35, 35, 35, 35, 35, 35, 35, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36

Offset: 0

N. J. A. Sloane, Jul 27 2016

Place k queens on an n X n board so that the total number of squares attacked/occupied by the queens is minimized.
If enough terms were known, would provide an upper bound for A250000. For if A250000(n) = Q then T(n,Q) <= n^2 - Q, or equivalently A274948(n,Q) >= Q.
Values n^2 - T(n,n) are given in A001366.
Let X(n) be the smallest number so that no matter how you place X queens, they attack every square. That is, X is the minimal number such that T(n,k) = n^2 for all k >= X. Then X = n^2 - T(n,1) + 1 = A274948(n,1) + 1 = n^2 - 3*n + 3. More generally, T(n,k') <= n^2-k if and only if k' <= n^2-T(n,k). For example, we may place 2 queens on two squares of a 4 X 4 board and leave 4^2-T(4,2)=3 squares not attacked, so we may place 3 queens on these 3 squares instead and leave those two squares not attacked, ergo, T(4,3)=16-2. - Andrey Zabolotskiy, Jul 29 2016

			The triangle begins:
0
0, 1,
0, 4, 4, 4, 4,
0, 7, 8, 9, 9, 9, 9, 9, 9, 9,
0, 10, 13, 14, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
0, 13, 18, 20, 21, 22, 23, 23, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
0, 16, 23, 27, 28, 30, 31, 32, 32, 33, 34, 34, 34, 34, 35, 35, 35, 35, 35, 35, 35, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36,
0, 19, 28, 33, 33, 38, 39, 42, 43, 43, 43, 44, 45, 45, 45, 45, 45, 47, 47, 47, 47, 47, 48, 48, 48, 48, 48, 48, 48, 48, 48, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49,
0, 22, 33, 39, 40, 47, 49, 51, 53, 54, 55, 56, 57, 57, 58, 58, 59, 59, 60, 60, 60, 60, 60, 60, 60, 61, 62, 62, 62, 62, 62, 62, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
0, 25, 38, 45, 45, 54, 57, 61, 62, 63, 67, 68, 69, 70, 71, 72, 72, 72, 72, 73, 74, 75, 75, 75, 75, 76, 76, 76, 77, 77, 77, 77, 77, 77, 77, 77, 77, 79, 79, 79, 79, 79, 79, 79, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81, 81,
0, 28, 43, 51, 52, 63, 67, 70, 74, 76, 78, 81, 82, 84, 85, 86, 87, 88, 88, 89, 90, 90, 90, 91, 91, 92, 92, 93, 93, 93, 93, 94, 94, 94, 95, 95, 95, 95, 96, 96, 96, 96, 96, 96, 96, 96, 96, 96, 96, 97, 98, 98, 98, 98, 98, 98, 98, 98, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
...
(Rows 6 through 10 from _Rob Pratt_, Aug 02 2016)
The entry T(4,3) = 14 is achieved by
OXOX
OOOX
AOOO
OOAO
since the two squares marked A are not attacked by the three queens at X.

Bernard Lemaire and Pavel Vitushinkiy, Placing n non dominating queens on the n X n chessboard. Part I, French Federation of Mathematical Games.
Bernard Lemaire and Pavel Vitushinkiy, Placing n non dominating queens on the n X n chessboard. Part II, French Federation of Mathematical Games.

Cf. A001366, A274948, A250000.
Cf. A075458 (minimal number of queens needed to attack all the squares of an n X n board).
Row 8 subtracted from 64 is A342151.

T(n,1) = 3*n-2 for n >= 1.

Corrections and more terms from Andrey Zabolotskiy, Jul 29 2016

More terms via integer linear programming from Rob Pratt, Aug 02 2016

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

Original entry on oeis.org

1, 1, 1, 3, 37, 1, 13, 638, 21, 1, 1, 1, 41, 588, 25872, 43, 22, 2

Offset: 1

N. J. A. Sloane

W. Ahrens, Mathematische Unterhaltungen und Spiele, second edition (1910), Vol. 1, p. 301.
W. W. R. Ball and H. S. M. Coxeter, Math'l Rec. and Essays, 13th Ed. Dover, p. 173.
Teresa W. Haynes, Stephen T. Hedetniemi and Michael A. Henning (eds.), Structures of Domination in Graphs, Springer, 2021. See Table 14 on p. 368.
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).

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 A002564 for number of distinct solutions.

A075458 gives number of queens required.

a(16)-a(18) from "Structures of Domination in Graphs" added by Andrey Zabolotskiy, Sep 02 2021

A274138 Triangle read by rows: 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, 2, 1, 2, 2, 2, 3, 1, 2, 2, 3, 3, 3, 1, 2, 3, 3, 3, 4, 4, 1, 2, 3, 3, 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, 6, 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, Jun 11 2016

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 a dominating set of Q(n X m) is the domination number, denoted by gamma(Q(n X m)).
Less formally, gamma(Q(n X m)) is the number of queens that are necessary and sufficient to all squares of the n X m chessboard be occupied or attacked.
Chessboard 8 X 11 is of special interest, because it cannot be dominated by 5 queens, although the larger boards 9 X 11, 10 X 11 and 11 X 11 are. It is conjectured that 8 X 11 is the only counterexample of this kind of monotonicity.

			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  2
5  |1  2  2  2  3
6  |1  2  2  3  3  3
7  |1  2  3  3  3  4  4
8  |1  2  3  3  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  6
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  6  7  7  7  8  8  8  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  8  8  9  9  9  9  9  9

Sandor Bozoki, Table of n, a(n) for n = 1..170
S. Bozóki, P. Gál, I. Marosi, W. D. Weakley, Domination of the rectangular queen’s graph, arXiv:1606.02060 [math.CO], 2016.
S. Bozóki, P. Gál, I. Marosi, W. D. Weakley, Domination of the rectangular queen’s graph, 2016.

Diagonal elements are in A075458: Domination number for queens' graph Q(n).

cp's OEIS Frontend

A140858 This sequence is identical with A075458.

Views

Author

Keywords

A075561 Domination number for kings' graph K(n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A006075 Minimal number of knights needed to cover an n X n board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A075324 Independent domination number for queens' graph Q(n).

Views

Author

Keywords

Examples

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

A002564 Number of different ways one can attack all squares on an n X n chessboard using the minimum number of queens.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A274947 Irregular triangle read by rows: T(n,k) (n>=0, 0 <= k <= n^2) = least number of squares attacked by k queens on an n X n board.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

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

Views

Author