The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A075458 Domination number for queens' graph Q(n). 11
1, 1, 1, 2, 3, 3, 4, 5, 5, 5, 5, 6, 7, 8, 9, 9, 9, 9, 10 (list; graph; refs; listen; history; text; internal format)



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


Table of n, a(n) for n=1..19.

S. Bozóki, P. Gál, I. Marosi, 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.

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.

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.

Sequence in context: A229835 A196155 A140858 * A332271 A267861 A253548

Adjacent sequences:  A075455 A075456 A075457 * A075459 A075460 A075461




N. J. A. Sloane, Oct 16 2002


a(19) from Peter Karpov, Mar 01 2016



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 7 19:09 EDT 2021. Contains 343652 sequences. (Running on oeis4.)