|
%I #20 Mar 04 2024 21:29:52
%S 1,1,1,2,3,4,4,5,5,6,7,8,9,10,11,12,12,13,14,15,15,16,17,18,18,19,19,
%T 20,21,22,23,24,25,26,27,28,29,30,30,31,32,33,34,35,36,37,37,38,39,40,
%U 40,41,42,43,44,45,46,47,47,48
%N a(n) is the diagonal domination number for the queen graph on an n X n chessboard.
%C a(n) is the smallest number of queens that can be placed on the diagonal of an n X n chessboard attacking all the cells on the chessboard. For large n the diagonal domination number exceeds the domination number.
%C The diagonal dominating set can be described by the set X of the x-coordinates of all the queens. Cockayne and Hedetniemi showed that for n greater than 1, set X has to be the complement to a midpoint-free even-sum set. Here midpoint-free means that the set doesn't contain an average of any two of its elements. Even-sum means that each sum of a pair of elements is even. Thus the problem of finding the diagonal domination number is equivalent to finding a largest midpoint-free even-sum set in the range 1-n.
%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 E. J. Cockayne and S. T. Hedetniemi, <a href="https://doi.org/10.1016/0097-3165(86)90012-9">On the diagonal queens domination problem</a>, J. Combin. Theory Ser. A, 42, (1986), 137-139.
%F For n > 1, a(n) = A003002(floor((n+1)/2)).
%e Consider a 9 X 9 chessboard. The largest midpoint-free even-sum set has size 4. For example: 1, 3, 7, and 9 form such a subset. Thus, the queen's position diagonal domination number is 5 and queens can be placed on the diagonal in rows 2, 4, 5, 6, and 8 to dominate the board.
%Y Cf. A003002.
%K nonn
%O 1,4
%A _Tanya Khovanova_ and PRIMES STEP junior group, Oct 28 2022
|
