2024/07/27 by Cristopher Moore, Moore, Cristopher, Stephan Mertens +1
Economics, Econometrics and Finance · Social Sciences · #05A15 #05C69 #American Constitutional Law and Politics #Combinatorics (math.CO) #Culture, Economy, and Development Studies #Economic Policies and Impacts #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2407.19344
openalex publication_date 2024/07/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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)\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 ± 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 Pn1× n2×⋯× nd(-1) = (-1)\lceil n1/2\rceil \lceil n2/2\rceil⋯ \lceil nd/2\rceil.