The m × n king graph consists of all locations on an m × 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 Pm × n(z) denote its domination polynomial, i.e., ∑S ⊆ V z|S| where the sum is over all dominating sets S. We prove that Pm × n(-1) = (-1)m/2 n/2. In particular, the number of dominating sets of even size and the number of odd size differs by ± 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 Pn₁× n₂×⋯× nd(-1) = (-1)n₁/2 n₂/2⋯ nd/2.
No takes yet. Share an insight, caveat, or question.
Moore et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: