A075458 - OEIS

%I #103 Feb 16 2025 08:32:47

%S 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

%N Domination number for queens' graph Q(n).

%C From _Dmitry Kamenetsky_, Sep 03 2019: (Start)

%C Minimum number of queens needed to occupy or attack all squares of an n X n chessboard.

%C a(n) >= ceiling(n/2) for all n, except n = 3, 11. See paper by Finozhenok and Weakley below.

%C 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)

%D W. W. R. Ball and H. S. M. Coxeter, "Math'l Rec. and Essays," 13th Ed. Dover, p. 173.

%D John Watkins, Across the Board: The Mathematics of Chessboard Problems (2004), pp. 113-137

%H William Herbert Bird, <a href="https://dspace.library.uvic.ca/handle/1828/8634">Computational methods for domination problems</a>, University of Victoria, 2017. See Table 5.1 on p. 114.

%H S. Bozóki, P. Gál, I. Marosi and W. D. Weakley, <a href="https://arxiv.org/abs/1606.02060">Domination of the rectangular queen's graph</a>, arXiv:1606.02060 [math.CO], 2016.

%H Domingos M. Cardoso, Inês Serôdio Costa, and Rui Duarte, <a href="https://arxiv.org/abs/2012.01992">Spectral properties of the n-Queens' Graphs</a>, arXiv:2012.01992 [math.CO], 2020. See p. 10.

%H Irene Choi, Shreyas Ekanathan, Aidan Gao, Tanya Khovanova, Sylvia Zia Lee, Rajarshi Mandal, Vaibhav Rastogi, Daniel Sheffield, Michael Yang, Angela Zhao, and Corey Zhao, <a href="https://arxiv.org/abs/2212.01468">The Struggles of Chessland</a>, arXiv:2212.01468 [math.HO], 2022.

%H Dmitry Finozhenok and W. Doug Weakley, <a href="https://ajc.maths.uq.edu.au/pdf/37/ajc_v37_p295.pdf">An Improved Lower Bound for Domination Numbers of the Queen’s Graph</a>, Australasian Journal of Combinatorics, vol. 37, 2007, p. 295-300.

%H Dmitry Kamenetsky, <a href="/A075458/a075458.txt">Best known solutions for n <= 26.</a>

%H Dmitry Kamenetsky, <a href="/A075458/a075458.m.txt">Matlab program to compute a(n) for small n.</a>

%H Dmitry Kamenetsky, <a href="/A075458/a075458.java.txt">Java program to compute the best known solutions.</a>

%H Matthew D. Kearse and Peter B. Gibbons, <a href="http://ajc.maths.uq.edu.au/pdf/23/ocr-ajc-v23-p253.pdf">Computational Methods and New Results for Chessboard Problems</a>, Australasian Journal of Combinatorics 23 (2001), 253-284.

%H Stephan Mertens, <a href="https://arxiv.org/abs/2401.00716">Domination Polynomial of the Rook Graph</a>, arXiv:2401.00716 [math.CO], 2024.

%H Patric R. J. Östergård and William D. Weakley, <a href="https://doi.org/10.37236/1573">Values of Domination Numbers of the Queen's Graph</a>, The Electronic Journal of Combinatorics, volume 8, issue 1, 2001.

%H M. A. Sainte-Laguë, <a href="http://www.numdam.org/issue/MSM_1926__18__1_0.pdf">Les Réseaux (ou Graphes)</a>, Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1926, p. 49.

%H A. Sinko and P. J. Slater, <a href="http://dx.doi.org/10.1016/j.disc.2007.08.065">Queen's domination using border squares and (A,B)-restricted domination</a>, Discrete Math., 308 (2008), 4822-4828.

%H Stan Wagon, <a href="http://www.jstor.org/stable/10.4169/college.math.j.45.4.278">Graph Theory Problems from Hexagonal and Traditional Chess</a>, The College Mathematics Journal, Vol. 45, No. 4, September 2014, pp. 278-287.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DominationNumber.html">Domination Number</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/QueenGraph.html">Queen Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/QueensProblem.html">Queens Problem</a>

%Y A002563 gives number of solutions.

%Y Cf. A006075, A075561, A189889.

%Y Cf. A075324 (independent domination number).

%K nonn,hard,more,changed

%O 1,4

%A _N. J. A. Sloane_, Oct 16 2002

%E a(19) from _Peter Karpov_, Mar 01 2016

%E a(20)-a(24) from Bird and a(25) from _Dmitry Kamenetsky_'s file added by _Andrey Zabolotskiy_, Sep 03 2021