On Generalizing the “Lights Out” Game and a Generalization of Parity Domination

Abstract

The Lights Out game on a graph $G$ is played as follows. Begin with a (not necessarily proper) coloring of $V(G)$ with elements of ${\mathbb{Z}}_2$. When a vertex is toggled, that vertex and all adjacent vertices change their colors from $0$ to $1$ or vice-versa. The game is won when all vertices have color $0$. The winnability of this game is related to the existence of a parity dominating set.
We generalize this game to ${\mathbb{Z}}_k$, $k\ge 2$, and use this to define a generalization of parity dominating sets. We determine all paths, cycles, and complete bipartite graphs in which the game over ${\mathbb{Z}}_k$ can be won regardless of the initial coloring, and we determine a constructive method for creating all caterpillar graphs in which the Lights Out game cannot always be won.