A381091 -id:A381091 - cp's OEIS frontend

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

Tanya Khovanova and PRIMES STEP junior group, Oct 28 2022

nonn

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

			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.

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.

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

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

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions