Journal of Integer Sequences, Vol. 24 (2021), Article 21.5.8

Knights and Liars on Graphs

Paul Tabatabai and Dieter P. Gruber
Polymer Competence Center Leoben GmbH
Roseggerstraße 12
8700 Leoben


We discuss the Knights and Liars problem, which is the problem of maximizing the number of red vertices in a red-blue-coloring of the vertices on a square grid, such that for each red vertex, exactly half of its neighbors are red, and for each blue vertex, not exactly half of its neighbors are red. We discuss the generalization of the problem to arbitrary graphs and discuss three integer programming formulations, by which we give results for grid graphs, torus grid graphs, triangular grid graphs, and graphs corresponding to the transitive closure of the boolean lattice. We give a full combinatorial treatment for two-dimensional grid graphs whose shorter interval-size is less than seven. We further prove that the decision version of the generalized problem is NP-complete.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A007980 A289362.)

Received July 19 2020; revised versions received March 21 2021; April 26 2021. Published in Journal of Integer Sequences, April 26 2021.

Return to Journal of Integer Sequences home page