

A075458


Domination number for queens' graph Q(n).


12



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

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


LINKS

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.
M. A. SainteLaguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, GauthierVillars, Paris, 1926, p. 49.


CROSSREFS



KEYWORD

nonn,hard,more


AUTHOR



EXTENSIONS



STATUS

approved



