Article in volume
Authors:
Title:
An extremal problem for the neighborhood Lights Out game
PDFSource:
Discussiones Mathematicae Graph Theory 44(3) (2024) 997-1021
Received: 2022-02-02 , Revised: 2022-11-28 , Accepted: 2022-11-30 , Available online: 2023-01-20 , https://doi.org/10.7151/dmgt.2481
Abstract:
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,\dots, \ell-1\}$ for
$\ell \in \mathbb{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 $\ell$). The game is won when every vertex has label 0. For any
$n \ge 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 $\ell$ is odd.
When $n$ and $\ell$ 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
References:
- A.T. Amin and P.J. Slater, Neighborhood domination with parity restrictions in graphs, Congr. Numer. 91 (1992) 19–30.
- 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 - C. Arangala, The $4 × n$ multistate Lights Out game, Math. Sci. Int. Res. J. 1 (2012) 10–13.
- C. Arangala and M. MacDonald, The $6 × n$ five color Lights Out game, J. Recreat. Math. 38 (2014) 38–44.
- C. Arangala, M. MacDonald and R. Wilson, Multistate lights out, Pi Mu Epsilon J. 14 (2014) 9–18.
- 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 - W.C. Brown, Matrices over Commutative Rings (Marcel Dekker, Inc., New York, 1993).
- 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 - 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 - A. Giffen and D.B. Parker, On generalizing the ``Lights Out" game and a generalization of parity domination, Ars Combin. 111 (2013) 273–288.
- J. Goldwasser and W. Klostermeyer, Maximization versions of ``Lights Out'' games in grids and graphs, Congr. Numer. 126 (1997) 99–111.
- A. Graf, A new graceful labeling for pendant graphs, Aequationes Math. 87 (2014) 135–145.
https://doi.org/10.1007/s00010-012-0184-4 - 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 - D.B. Parker., The Lights Out game on subdivided caterpillars, Ars Combin. 136 (2018) 347–356.
- K. Sutner, The $\sigma$-game and cellular automata, Amer. Math. Monthly 97 (1990) 24–34.
https://doi.org/10.1080/00029890.1990.11995540
Close