Computational methods and new results for chessboard problems (Q2712528)

The authors describe some computational methods for solving domination problems on chessboard graphs and present some new computational results on the domination and irredundance numbers of the queen's graph \(Q_n\) and king's graph \(K_n\). The basic strategies are backtracking, reduction and probabilistic local search. Their new results are \(\gamma(Q_{14})=8\), \(\gamma(Q_{15})=\gamma(Q_{16})=9\), \(\gamma(Q_{19})=10\), \(i(Q_{18})=10\), \(10\leq i(Q_{19})\leq 11\), \(\text{ir}(Q_n)=\gamma(Q_n)\) for \(1\leq n\leq 13\), \(\text{IR}(Q_9)=\Gamma(Q_9)=13\), \(\text{IR}(Q_{10})=\Gamma(Q_{10})=15\), \(\gamma(Q_{4k+1})=2k+1\) for \(k=16,18,20\) and \(21\), \(i(Q_{22})\leq 12\), \(\text{IR}(K_{8})=17\), \(\text{IR}(K_{9})=25\), \(\text{IR}(K_{10})=27\) and IR\((K_{11})=36\). Furthermore, they calculate the number of non-isomorphic minimum dominating and independent dominating sets in the queen's graph for \(n\leq 15\) and \(n\leq 18\), respectively.