Computational methods and new results for chessboard problems

Abstract

We describe various computing techniques for tackling chessboard domination problems and apply these to the determination of domination and irredundance numbers for queens’ and kings’ graphs. In particular we show that γ(Q15) = γ(Q16) = 9, confirm that γ(Q17) =γ(Q18) = 9, show that γ(Q19) = 10, show that i(Q18) = 10, improve the bound for i(Q19) to10 ≤ i(Q19) ≤ 11, show that ir(Qn) =γ(Qn) for 1 ≤ n ≤ 13, show that IR(Q9) =Γ(Q9) = 13 and that IR(Q10) =Γ(Q10) = 15, show that γ(Q4k+1) =2k +1for16 ≤ k ≤ 21, improve the bound for i(Q22) toi(Q22) ≤ 12, and show that IR(K8) =17,IR(K9) =25,IR(K10) = 27, and IR(K11) = 36.