Lights Out in graphs: turning off the lights in the slightest way

• Fernanda Couto UFRRJ
• Ighor Bruno de Brito UFRRJ
• Willian de Assis Sento Sé UFRRJ

DOI: https://doi.org/10.5753/etc.2022.223319

Abstract

Lights Out is an eletronic puzzle whose goal is to find a set of buttons that, when pressed, turns off all the lights on the board. In this work, we consider the generalization of the game whose input is a graph and we focus on its minimize version, whose goal is to determine the minimum number of vertices that must be activated in order to turn all graph lights off. We deal with Caterpillar graphs, Flower Snarks and Goldberg Snarks. To help us on obtaining the results, a software that simulates the game for any input data has been implemented as well as a brute-force algorithm that solves the minimize version of Lights Out game.

Keywords: Lights Out, Snark, Grafos

References

Berman, A., Borer, F., and Hungerbühler, N. (2019). Lights out on graphs. arXiv:1903.06942.

Fleischer, R. and Yu, J. (2013). A survey of the game lights out! LNCS, 8066.

Isaacs, R. (1975). Infinite families of nontrivial trivalent graphs which are not tait colorable. The American Mathematical Monthly.

Sutner, K. (1988). Additive automata on graphs. complex systems 2. Stevens Institute of Technology.