Search

Neighborhood Lights Out is a game played on graphs. Begin with a graph and a vertex labeling of the graph from the set {0, 1, 2, . . ., ℓ - 1} for ℓ ∈ N. The game is played by toggling vertices: when a vertex is toggled, that vertex and each of its neighbors has its label increased by 1 (modulo ℓ). The game is won when every vertex has label 0. For any n ≥ 2 it is clear that one cannot win the game on Kn unless the initial labeling assigns all vertices the same label. Given that Kn has the maximum number of edges of any simple graph on n vertices it is natural to ask how many edges can be in a graph so that the Neighborhood Lights Out game is winnable regardless of the initial labeling. We find the maximum number of edges a winnable n-vertex graph can have when at least one of n and ℓ is odd. When n and ℓ are both even we find the maximum size in two additional cases. The proofs of our results require us to introduce a new version of the Lights Out game that can be played given any square matrix. [ABSTRACT FROM AUTHOR]