A075561 -id:A075561 - cp's OEIS frontend

A378420 Irregular triangle read by rows: T(n,k) is the coefficient of x^k in the domination polynomial of the n X n king graph (n>=1, A075561(n)<=k<=n^2).

1, 4, 6, 4, 1, 1, 10, 48, 106, 122, 84, 36, 9, 1, 256, 1536, 4480, 8320, 10896, 10560, 7744, 4320, 1816, 560, 120, 16, 1, 79, 1593, 14672, 81524, 307244, 842506, 1764068, 2918828, 3909834, 4311034, 3955232, 3038092, 1957940, 1056965, 475304, 176256, 53046, 12646

Offset: 1

Eric W. Weisstein, Nov 25 2024

Sum_{k=A075561(n)..n^2} T(n,k) = A133791(n).

T(n,n^2) = 1.

			D(1)=x
D(2)=4*x+6*x^2+4*x^3+x^4
D(3)=x+10*x^2+48*x^3+106*x^4+122*x^5+84*x^6+36*x^7+9*x^8+x^9
D(4)=256*x^4+1536*x^5+4480*x^6+8320*x^7+10896*x^8+10560*x^9+7744*x^10+4320*x^11+1816*x^12+560*x^13+120*x^14+16*x^15+x^16

Eric W. Weisstein, Table of n, a(n) for n = 1..3333
Stephan Mertens, Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph, arXiv:2408.08053 [math.CO], Aug 2024.
Eric Weisstein's World of Mathematics, Dominating Set.
Eric Weisstein's World of Mathematics, Domination Number.
Eric Weisstein's World of Mathematics, Domination Polynomial.
Eric Weisstein's World of Mathematics, King Graph.

Cf. A075561 (domination number of the n X n king graph).
Cf. A133791 (number of dominating sets in the n X n king graph).
Cf. A000290 (vertex count of the n X n king graph = n^2).

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

Original entry on oeis.org

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

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

A350815 Array read by antidiagonals: T(m,n) is the number of minimum dominating sets in the m X n king graph.

Original entry on oeis.org

1, 2, 2, 1, 4, 1, 4, 2, 2, 4, 3, 16, 1, 16, 3, 1, 12, 4, 4, 12, 1, 8, 4, 3, 256, 3, 4, 8, 4, 64, 1, 144, 144, 1, 64, 4, 1, 32, 8, 16, 79, 16, 8, 32, 1, 13, 8, 4, 4096, 9, 9, 4096, 4, 8, 13, 5, 208, 1, 1024, 1656, 1, 1656, 1024, 1, 208, 5, 1, 80, 13, 64, 408, 64, 64, 408, 64, 13, 80, 1

Offset: 1

Andrew Howroyd, Jan 17 2022

The minimum size of a dominating set is the domination number which in the case of an m X n king graph is given by (ceiling(m/3) * ceiling(n/3)).

			Table begins:
============================================
m\n | 1  2  3    4    5   6      7     8
----+---------------------------------------
  1 | 1  2  1    4    3   1      8     4 ...
  2 | 2  4  2   16   12   4     64    32 ...
  3 | 1  2  1    4    3   1      8     4 ...
  4 | 4 16  4  256  144  16   4096  1024 ...
  5 | 3 12  3  144   79   9   1656   408 ...
  6 | 1  4  1   16    9   1     64    16 ...
  7 | 8 64  8 4096 1656  64 243856 29744 ...
  8 | 4 32  4 1024  408  16  29744  3600 ...
     ...

Stephan Mertens, Table of n, a(n) for n = 1..946 (first 276 terms from Andrew Howroyd)
Stephan Mertens, Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph, arXiv:2408.08053 [math.CO], Aug 2024.
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Minimum Dominating Set

Rows 1..3 are A347633, A350816, A347633.
Main diagonal is A347554.
Cf. A075561, A218663 (dominating sets), A286849 (minimal dominating sets), A303335, A350818, A350819.

T(n,m) = T(m,n).
T(3*m, 3*n) = 1; T(3*m+1, 3*n) = (m^2 + 5*m + 2)^n; T(3*m+2, 3*n) = (m+2)^n.
T(3*m-1, 3*n-1) = A350819(m, n).

A211547 The squares n^2, n >= 0, each one written three times.

Original entry on oeis.org

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

Offset: 0

Clark Kimberling, Apr 15 2012

Number of ordered triples (w,x,y) with all terms in {1,...,n} and 2w=3x+3y.

For a guide to related sequences, see A211422.

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,0,2,-2,0,-1,1).

Cf. A075561, A211422, A211435 (triply repeated triangular numbers).

t[n_] := t[n] = Flatten[Table[-2 w + 3 x + 3 y, {w, 1, n}, {x, 1, n}, {y, 1, n}]]
c[n_] := Count[t[n], 0]
t = Table[c[n], {n, 0, 60}](*A211547, squares thrice*)
FindLinearRecurrence[t]
LinearRecurrence[{1,0,2,-2,0,-1,1},{0,0,0,1,1,1,4},60] (* Ray Chandler, Aug 02 2015 *)

concat(vector(3), Vec(x^3*(1 + x)*(1 - x + x^2) / ((1 - x)^3*(1 + x + x^2)^2) + O(x^40))) \\\ Colin Barker, Dec 02 2017

a(n) = a(n-1) + 2*a(n-3) - 2*a(n-4) - a(n-6) + a(n-7).
G.f.: x^3*(1 + x)*(1 - x + x^2) / ((1 - x)^3*(1 + x + x^2)^2). - Colin Barker, Dec 02 2017
a(n) = A075561(n-2) for n > 2. - Georg Fischer, Oct 23 2018
E.g.f.: exp(-x/2)*(exp(3*x/2)*(5 + 3*x*(x - 1)) - 5*cos(sqrt(3)*x/2) - sqrt(3)*(3 + 4*x)*sin(sqrt(3)*x/2))/27. - Stefano Spezia, Oct 17 2022

Definition simplified by N. J. A. Sloane, Nov 17 2020. Also the old version said "squares repeated three times", which was at best ambiguous, and strictly speaking was incorrect, since "squares repeated" is 0, 0, 1, 1, 4, 4, 9, 9, ... .

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

A347554 Number of minimum dominating sets in the n X n king graph.

Original entry on oeis.org

1, 4, 1, 256, 79, 1, 243856, 3600, 1, 581571283, 281585, 1, 2722291223553, 32581328, 1, 21706368614058886, 5112264019, 1, 268740319616196074546, 1028516654620, 1, 4839916638142874877046813

Offset: 1

Eric W. Weisstein, Sep 06 2021

a(3*n) = 1 for all n, since the 3n X 3n king graph has domination number n^2 and the only way to achieve this is if each of the n^2 kings is placed in the middle of its own 3 X 3 square.

Stephan Mertens, Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph, arXiv:2408.08053 [math.CO], Aug 2024.
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Minimum Dominating Set
Eric W. Weisstein, Unique minimum dominating set on a 3n X 3n king graph

Main diagonal of A350815.

Cf. A075561 (domination number of the n X n king graph), A133791, A286881.

a(7)-a(12) from Andrew Howroyd, Jan 17 2022

a(13)-a(22) from Stephan Mertens, Aug 18 2024

A370428 Connected domination number of the n X n king graph.

Original entry on oeis.org

1, 1, 1, 4, 5, 8, 12, 15, 20, 24, 28, 33, 39, 46, 52, 58

Offset: 1

Alexander D. Healy, Feb 24 2024

In other words, a(n) is the minimum number of kings that can be placed on an n X n chessboard such that (i) the occupied squares form a single connected component, and (ii) every square is either occupied by a king or adjacent to one that is.

a(17) <= 67; a(18) <= 75; a(19) <= 83; a(20) <= 92.

Alexander D. Healy, Examples of (near-)optimal connected dominating sets for n <= 20.
Eric Weisstein's World of Mathematics, Connected Domination Number.
Eric Weisstein's World of Mathematics, King Graph.

Cf. A075561, A289180, A302401, A369692.

Cf. A382206 (numbers of minimum connected dominating sets).

a(13)-a(16) from Andrew Howroyd, Feb 25 2024

A379726 Minimum number of kings that must be placed on an n X n chessboard such that each square is attacked or occupied by at least two kings.

Original entry on oeis.org

2, 3, 8, 8, 10, 18, 18, 21, 32, 32, 36, 50, 50, 55, 72, 72, 78, 98, 98, 105, 128, 128, 136, 162, 162, 171, 200, 200, 210, 242, 242, 253, 288, 288, 300, 338, 338, 351, 392, 392, 406, 450, 450, 465, 512, 512, 528, 578, 578, 595, 648, 648, 666, 722, 722, 741, 800, 800, 820, 882, 882, 903, 968, 968, 990, 1058, 1058, 1081, 1152, 1152, 1176, 1250, 1250, 1275, 1352, 1352, 1378, 1458, 1458, 1485, 1568, 1568, 1596, 1682, 1682, 1711, 1800, 1800, 1830, 1922, 1922, 1953, 2048, 2048, 2080, 2178, 2178, 2211, 2312

Offset: 2

Matthew Scroggs, Dec 31 2024

nonn

At most one king can be placed on each square.
Every third term is conjectured to be A014105. Other terms are A001105. A093353 is conjectured to be this sequence with repeated terms removed.
The above conjectures are true (see Beveridge link). - Colin Beveridge, Jan 13 2025

			For a 3 by 3 chessboard, the three kings could be placed like this (where o is an empty square and k is a king):
   ooo
   kkk
   ooo
For a 4 by 4 chessboard, the kings could be placed like this:
   oooo
   kkkk
   okko
   okko

Rob Pratt, Table of n, a(n) for n = 2..100
Colin Beveridge, Proof of the case where n is a multiple of 3
Matthew Scroggs, December 23
Matthew Scroggs, Friendly squares
Matthew Scroggs, Python code to compute A379726
Puzzling StackExchange, Minimum Number of Squares to Color
Dominic McCarty, Illustration of a(n) for n = 2..100

Cf. A001105, A014105, A075561, A093353, A379759, A379766.

If n is not a multiple of 3, a(n) = 2*floor((n+2)/3)^2.
If n is a multiple of 3, it is conjectured that a(n)=2*(n/3)^2+n/3.
The above conjectures are true (see Beveridge link). - Colin Beveridge, Jan 13 2025

a(15)-a(100) via integer linear programming by Rob Pratt, Jan 02 2025

A379759 Minimum number of kings that must be placed on an n X n chessboard such that each square is attacked or occupied by at least three kings.

Original entry on oeis.org

3, 5, 12, 12, 16, 27, 27, 33, 48, 48, 56, 75, 75, 85, 108, 108, 120, 147, 147, 161, 192, 192, 208, 243, 243, 261, 300, 300, 320, 363, 363, 385, 432, 432, 456, 507, 507, 533, 588, 588, 616, 675, 675, 705, 768, 768, 800, 867, 867, 901, 972, 972, 1008, 1083, 1083

Offset: 2

Matthew Scroggs, Jan 02 2025

nonn

At most one king can be placed on each square.

			For a 3 by 3 chessboard, the five kings could be placed like this:
   oko
   kkk
   oko
For a 4 by 4 chessboard, the kings could be placed like this:
   okko
   kkkk
   kkkk
   okko
where o is an empty square and k is a king.

Dominic McCarty, Table of n, a(n) for n = 2..100
Matthew Scroggs, Python code to compute A379759
Dominic McCarty, Illustration of a(n) for n = 2...100
Dominic McCarty, Java program for A379759

Cf. A075561, A379726, A379766.

It appears that a(3n+1) = a(3n+2) - Dominic McCarty, Jan 17 2025

a(9)-a(100) from Dominic McCarty, Jan 17 2025

cp's OEIS Frontend

A378420 Irregular triangle read by rows: T(n,k) is the coefficient of x^k in the domination polynomial of the n X n king graph (n>=1, A075561(n)<=k<=n^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A350815 Array read by antidiagonals: T(m,n) is the number of minimum dominating sets in the m X n king graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A211547 The squares n^2, n >= 0, each one written three times.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A347554 Number of minimum dominating sets in the n X n king graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A370428 Connected domination number of the n X n king graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A379726 Minimum number of kings that must be placed on an n X n chessboard such that each square is attacked or occupied by at least two kings.

Views