Domination by kings is oddly even

Abstract

The $m\times n$ king graph consists of all locations on an $m\times n$ chessboard, where edges are legal moves of a chess king. %where each vertex represents a square on a chessboard and each edge is a legal move. Let $P_{m\times n}(z)$ denote its domination polynomial, i.e., ${\sum }_{S\subseteq V}{z}^{|S|}$ where the sum is over all dominating sets $S$. We prove that $P_{m\times n}(-1)=(-1{)}^{\lceil m/2\rceil \lceil n/2\rceil }$. In particular, the number of dominating sets of even size and the number of odd size differs by $\pm 1$. %The numbers can not be equal because the total number of dominating sets is always odd. This property does not hold for king graphs on a cylinder or a torus, or for the grid graph. But it holds for $d$-dimensional kings, where $P_{n_1\times n_2\times \cdots \times n_d}(-1)=(-1{)}^{\lceil n_1/2\rceil \lceil n_2/2\rceil \cdots \lceil n_d/2\rceil }$.

8 pages, 3 figures, 3 tables