cp's OEIS Frontend

A358062 a(n) is the diagonal domination number for the queen graph on an n X n chessboard.

%I A358062 #40 Jun 27 2025 17:24:26
%S A358062 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 A358062 20,21,22,23,24,25,26,27,28,29,30,30,31,32,33,34,35,36,37,37,38,39,40,
%U A358062 40,41,42,43,44,45,46,47,47,48
%N A358062 a(n) is the diagonal domination number for the queen graph on an n X n chessboard.
%C A358062 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 A358062 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.
%C A358062 a(n) agrees with the connected domination number up to n = 11 but differs for n = 12. - _Eric W. Weisstein_, Mar 27 2025
%H A358062 Eric W. Weisstein, <a href="/A358062/b358062.txt">Table of n, a(n) for n = 1..211</a>
%H A358062 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 A358062 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.
%H A358062 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/ConnectedDominatingSet.html">Connected Dominating Set</a>.
%H A358062 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/QueenGraph.html">Queen Graph</a>.
%F A358062 For n > 1, a(n) = n - A003002(ceiling(n/2)). - _Eric W. Weisstein_, Mar 07 2025
%e A358062 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 A358062 Cf. A003002 (size of largest Salem-Spencer set in [1..n]).
%Y A358062 Cf. A373394 (numbers of minimum connected dominating sets of n X n queen graph).
%Y A358062 Cf. A381091 (connected domination number of n X n queen graph).
%K A358062 nonn
%O A358062 1,4
%A A358062 _Tanya Khovanova_ and PRIMES STEP junior group, Oct 28 2022
%E A358062 Formula corrected and terms added based on A003002 by _Eric W. Weisstein_, Mar 07 2025