Lights Out on finite graphs
type: Item
instance of: scholarly article
title: Lights Out on finite graphs
zbMATH Open document ID: 1216.05086
author: Stephanie P. Edwards
author: Victoria Elandt
author: Nicholas James
author: Zachary Mitchell
author: Kathryn E. Johnson
author: Darin R. Stephenson
published in: Involve
publication date: 2010-09-09T00:00:00Z
review text: A popular game on graphs, known as ``Lights Out!'', starts with an assignment of 0 or 1 to each vertex of a finite graph \(G\). A move consists of choosing a vertex and then adding \(1 \pmod 2\) to the value of that vertex as well as to those of its neighbors. The object of the game is to find a sequence of moves that results in labeling all vertices of the graph 0. When this is possible, the initial labeling is said to be winnable. The existence of such a sequence of moves is related to the existence of an all-parity dominating set [see \textit{A. T. Amin} and \textit{P. J. Slater}, J. Comb. Math. Comb. Comput. 20, 53--63 (1996; Zbl 0845.05029)]. This game was generalized by A. Giffen and D. Parker (2009 preprint) by allowing the labels to be any value in \({\mathbb{Z}}_k\), where addition is now modulo \(k\). A graph \(G\) is said to be \textit{always winnable} (AW) over \({\mathbb{Z}}_k\) if every initial labeling of \(G\) is winnable. This paper considers this more general game and investigates properties of AW graphs over \({\mathbb{Z}}_k\). In particular, the authors characterize AW spider graphs (Theorem 3.4) and AW generalized theta graphs (Theorem 4.4). These results are obtained by first characterizing all winning labelings for sub-collections of these graphs. The authors also prove that a graph \(G\) is AW over \({\mathbb{Z}}_k\) if and only if \(G\) is AW over \({\mathbb{Z}}_p\) for every prime factor \(p\) of \(k\) (Proposition 2.2 and Corollary 2.3), and generalize the construction of Amin and Slater (1996) of AW trees over \({\mathbb{Z}}_2\) to produce AW trees over \({\mathbb{Z}}_p\), where \(p\) is prime (Theorem 5.3).
reviewed by: Italo Simonelli
Mathematics Subject Classification ID: 05C57
Mathematics Subject Classification ID: 91A43
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 5781522
zbMATH Keywords: Lights Out
zbMATH Keywords: parity domination
zbMATH Keywords: always winnable graph
MaRDI profile type: Publication
full work available at URL: involve.2010.3.17
OpenAlex ID: W2104541075
DOI: 10.2140/INVOLVE.2010.3.17
description: scientific article; zbMATH DE number 5781522