|
%I #90 Jan 05 2024 13:26:23
%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="http://mathworld.wolfram.com/DominationNumber.html">Domination Number</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/QueenGraph.html">Queen Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/QueensProblem.html">Queens Problem</a>
%Y A002563 gives number of solutions.
%Y Cf. A006075, A075561, A189889.
%K nonn,hard,more
%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
|
