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

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, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 30, 31, 32, 33, 34, 35, 36, 37, 37, 38, 39, 40, 40, 41, 42, 43, 44, 45, 46, 47, 47, 48

Offset: 1

Author

Tanya Khovanova and PRIMES STEP junior group, Oct 28 2022

Keywords

• nonn

Comments

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.

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.

a(n) agrees with the connected domination number up to n = 11 but differs for n = 12. - Eric W. Weisstein, Mar 27 2025

Examples

			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.
		

Links

• Eric W. Weisstein, Table of n, a(n) for n = 1..211
• 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.
• E. J. Cockayne and S. T. Hedetniemi, On the diagonal queens domination problem, J. Combin. Theory Ser. A, 42, (1986), 137-139.
• Eric Weisstein's World of Mathematics, Connected Dominating Set.
• Eric Weisstein's World of Mathematics, Queen Graph.

Crossrefs

Cf. A003002 (size of largest Salem-Spencer set in [1..n]).

Cf. A373394 (numbers of minimum connected dominating sets of n X n queen graph).

Cf. A381091 (connected domination number of n X n queen graph).

Formula

For n > 1, a(n) = n - A003002(ceiling(n/2)). - Eric W. Weisstein, Mar 07 2025

Extensions

Formula corrected and terms added based on A003002 by Eric W. Weisstein, Mar 07 2025