A002563 -id:A002563 - 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

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

A002565 Number of non-isomorphic ways to attack all squares on an n X n chessboard using the smallest possible number of queens with each queen attacking at least one other.

Original entry on oeis.org

0, 2, 5, 3, 15, 150, 5, 56, 3, 39, 681

Offset: 1

N. J. A. Sloane

Differs from A002563 and A002567 in that each queen is attacking at least one other queen. - Sean A. Irvine, Apr 05 2014

The Sainte-Laguë paper has "a(6)=140?". - Sean A. Irvine, Apr 05 2014

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

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]

Cf. A002566 (all solutions for attacking queens). - Sean A. Irvine, Apr 05 2014

a(6) corrected and a(9)-a(11) from Sean A. Irvine, Apr 05 2014

Better name from Sean A. Irvine, Apr 05 2014

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

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

A002565 Number of non-isomorphic ways to attack all squares on an n X n chessboard using the smallest possible number of queens with each queen attacking at least one other.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions