LIGHTS OUT! on graph products over the ring of integers modulo k

Main Article Content

Ryan Munter
Travis Peters


LIGHTS OUT! is a game played on a finite, simple graph. The vertices of the graph are the lights, which may be on or off, and the edges of the graph determine how neighboring vertices turn on or off when a vertex is pressed. Given an initial configuration of vertices that are on, the object of the game is to turn all the lights out. The traditional game is played over $\mathbb{Z}_2$, where the vertices are either lit or unlit, but the game can be generalized to $\mathbb{Z}_k$, where the lights have different colors. Previously, the game was investigated on Cartesian product graphs over $\mathbb{Z}_2$. We extend this work to $\mathbb{Z}_k$ and investigate two other fundamental graph products, the direct (or tensor) product and the strong product. We provide conditions for which the direct product graph and the strong product graph are solvable based on the factor graphs, and we do so using both open and closed neighborhood switching over $\mathbb{Z}_k$.

Article Details