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,4

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

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.

Formula

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

Example

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.

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

Sequence in context: A071991 A276952 A096336 * A081609 A337020 A351519

Adjacent sequences: A358059 A358060 A358061 * A358063 A358064 A358065

Keyword

nonn

Author

Tanya Khovanova and PRIMES STEP junior group, Oct 28 2022

Extensions

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

Status

approved