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.

Links

Table of n, a(n) for n=1..60.

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.

Formula

For n > 1, a(n) = A003002(floor((n+1)/2)).

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.

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

Status

approved