2023/04/13 by Karandikar, Archit, Dutta, Akashnil
#05B40 (Primary) 52C15 #11H31 (Secondary) #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2304.06620
The Queen's Domination problem, studied for over 160 years, poses the following question: What is the least number of queens that can be arranged on a m × n chessboard so that they either attack or occupy every cell? We propose a novel relaxation of the Queen's Domination problem and show that it is exactly solvable on both square and rectangular chessboards. As a consequence, we improve on the best known lower bound for rectangular chessboards in ≈ 12.5% of the non-trivial cases. As another consequence, we simplify and generalize the proofs for the best known lower-bounds for Queen's Domination of square n × n chessboards for n ≡ \0,1,2\ \mod 4 using an elegant idea based on a convex hull. Finally, we show some results and make some conjectures towards the goal of simplifying the long complicated proof for the best known lower-bound for square boards when n ≡ 3 \mod 4 (and n > 11). These simple-to-state conjectures may also be of independent interest.