Geodesic
An extremal problem for the neighborhood Lights Out game
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 997-1021 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2024},
     volume = {44},
     number = {3},
     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
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
%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/

[1] A.T. Amin and P.J. Slater, Neighborhood domination with parity restrictions in graphs, Congr. Numer. 91 (1992) 19–30.

[2] M. Anderson and T. Feil, Turning Lights Out with linear algebra, Math. Mag. 71(4) (1998) 300–303. https://doi.org/10.1080/0025570X.1998.11996658

[3] C. Arangala, The 4 × n multistate Lights Out game, Math. Sci. Int. Res. J. 1 (2012) 10–13.

[4] C. Arangala and M. MacDonald, The 6 × n five color Lights Out game, J. Recreat. Math. 38 (2014) 38–44.

[5] C. Arangala, M. MacDonald and R. Wilson, Multistate lights out, Pi Mu Epsilon J. 14 (2014) 9–18.

[6] L.E. Ballard, E.L. Budge and D.R. Stephenson, Lights Out for graphs related to one another by constructions, Involve 12 (2019) 181–201. https://doi.org/10.2140/involve.2019.12.181

[7] W.C. Brown, Matrices over Commutative Rings (Marcel Dekker, Inc., New York, 1993).

[8] D. Craft, Z. Miller and D. Pritikin, A solitaire game played on 2-colored graphs, Discrete Math. 309 (2009) 188–201. https://doi.org/10.1016/j.disc.2007.12.069

[9] S. Edwards, V. Elandt, N. James, K. Johnson, Z. Mitchell and D. Stephenson, Lights Out on finite graphs, Involve 3 (2010) 17–32. https://doi.org/10.2140/involve.2010.3.17

[10] A. Giffen and D.B. Parker, On generalizing the ``Lights Out" game and a generalization of parity domination, Ars Combin. 111 (2013) 273–288.

[11] J. Goldwasser and W. Klostermeyer, Maximization versions of ``Lights Out'' games in grids and graphs, Congr. Numer. 126 (1997) 99–111.

[12] A. Graf, A new graceful labeling for pendant graphs, Aequationes Math. 87 (2014) 135–145. https://doi.org/10.1007/s00010-012-0184-4

[13] D.B. Parker and V. Zadorozhnyy, A group-labeling version of the Lights Out game, Involve 14 (2021) 541–554. https://doi.org/10.2140/involve.2021.14.541

[14] D.B. Parker., The Lights Out game on subdivided caterpillars, Ars Combin. 136 (2018) 347–356.

[15] K. Sutner, The \sigma-game and cellular automata, Amer. Math. Monthly 97 (1990) 24–34. https://doi.org/10.1080/00029890.1990.11995540