Lights Out on finite graphs (Q992526)

A popular game on graphs, known as ``Lights Out!'', starts with an assignment of 0 or 1 to each vertex of a finite graph \(G\). A move consists of choosing a vertex and then adding \(1 \pmod 2\) to the value of that vertex as well as to those of its neighbors. The object of the game is to find a sequence of moves that results in labeling all vertices of the graph 0. When this is possible, the initial labeling is said to be winnable. The existence of such a sequence of moves is related to the existence of an all-parity dominating set [see \textit{A. T. Amin} and \textit{P. J. Slater}, J. Comb. Math. Comb. Comput. 20, 53--63 (1996; Zbl 0845.05029)]. This game was generalized by A. Giffen and D. Parker (2009 preprint) by allowing the labels to be any value in \({\mathbb{Z}}_k\), where addition is now modulo \(k\). A graph \(G\) is said to be \textit{always winnable} (AW) over \({\mathbb{Z}}_k\) if every initial labeling of \(G\) is winnable. This paper considers this more general game and investigates properties of AW graphs over \({\mathbb{Z}}_k\). In particular, the authors characterize AW spider graphs (Theorem 3.4) and AW generalized theta graphs (Theorem 4.4). These results are obtained by first characterizing all winning labelings for sub-collections of these graphs. The authors also prove that a graph \(G\) is AW over \({\mathbb{Z}}_k\) if and only if \(G\) is AW over \({\mathbb{Z}}_p\) for every prime factor \(p\) of \(k\) (Proposition 2.2 and Corollary 2.3), and generalize the construction of Amin and Slater (1996) of AW trees over \({\mathbb{Z}}_2\) to produce AW trees over \({\mathbb{Z}}_p\), where \(p\) is prime (Theorem 5.3).