Geodesic
An extremal problem for the neighborhood Lights Out game
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 997-1021

Voir la notice de l'article provenant de la source Library of Science

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 𝓁∈ℕ. 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 K_n unless the initial labeling assigns all vertices the same label. Given that K_n 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.
Keywords: Lights Out, light-switching game, winnability, extremal graph theory, linear algebra 
@article{DMGT_2024_44_3_a10,
     author = {Keough, Lauren and Parker, Darren B.},
     title = {An extremal problem for the neighborhood {Lights} {Out} game},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {997--1021},
     publisher = {mathdoc},
     volume = {44},
     number = {3},
     year = {2024},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a10/}
}
TY  - JOUR
AU  - Keough, Lauren
AU  - Parker, Darren B.
TI  - An extremal problem for the neighborhood Lights Out game
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 997
EP  - 1021
VL  - 44
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a10/
LA  - en
ID  - DMGT_2024_44_3_a10
ER  - 
%0 Journal Article
%A Keough, Lauren
%A Parker, Darren B.
%T An extremal problem for the neighborhood Lights Out game
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 997-1021
%V 44
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a10/
%G en
%F DMGT_2024_44_3_a10
Keough, Lauren; Parker, Darren B. An extremal problem for the neighborhood Lights Out game. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 997-1021. http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a10/