login
A075458
Domination number for queens' graph Q(n).
15
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,4
COMMENTS
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)
REFERENCES
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
LINKS
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.
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
CROSSREFS
A002563 gives number of solutions.
Cf. A075324 (independent domination number).
Sequence in context: A229835 A196155 A140858 * A332271 A350255 A267861
KEYWORD
nonn,hard,more
AUTHOR
N. J. A. Sloane, Oct 16 2002
EXTENSIONS
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
STATUS
approved