Does the lit-only restriction make any difference for the \(\sigma \)-game and \(\sigma ^+\)-game?
type: Item
instance of: scholarly article
title: Does the lit-only restriction make any difference for the \(\sigma \)-game and \(\sigma ^+\)-game?
zbMATH Open document ID: 1169.91011
author: Xinmao Wang
author: Yaokun Wu
author: John Goldwasser
published in: European Journal of Combinatorics
publication date: 2009-06-17T00:00:00Z
review text: Each vertex in a simple graph is in one of two states: ``on'' or ``off''. The set of all on vertices is called a configuration. In the \(\sigma \)-game, ``pushing'' a vertex \(v\) changes the state of all vertices in the open neighborhood of \(v\), while in the \(\sigma ^{+}\)-game pushing \(v\) changes the state of all vertices in its closed neighborhood. The reachability question for these two games is to decide whether a given configuration can be reached from a given starting configuration by a sequence of pushes. The lit-only restriction allows a vertex to be pushed only if it is in the on state. It is shown that the lit-only restriction can make a big difference for reachability in the \(\sigma \)-game, but has essentially no effect in the \(\sigma ^{+}\)-game.
reviewed by: Giacomo Bonanno
Mathematics Subject Classification ID: 91A43
Mathematics Subject Classification ID: 91A46
zbMATH DE Number: 5565523
zbMATH Keywords: lit-only sigma game
zbMATH Keywords: reachability
zbMATH Keywords: configuration
zbMATH Keywords: toggle
zbMATH Keywords: line graph
zbMATH Keywords: orbit
MaRDI profile type: Publication
full work available at URL: j.ejc.2008.09.020
OpenAlex ID: W2031414850
cites work: Complexity of reachability problems for finite discrete dynamical systems
cites work: On the complexity of dominating set problems related to the minimum all-ones problem
cites work: Q4653767
cites work: The Minimum All-Ones Problem for Trees
cites work: Extended Vogan diagrams
cites work: A quick proof on the equivalence classes of extended Vogan diagrams
cites work: On characterization of state transition graph of additive cellular automata based on depth
cites work: Universal configurations in light-flipping games
cites work: Eriksson's numbers game and finite Coxeter groups
cites work: Note on the lamp lighting problem
cites work: Reachability is decidable in the numbers game
cites work: Q4536689
cites work: Q4407707
cites work: Puzzlers' tribute. A feast for the mind
cites work: Q4393318
cites work: Q3378225
cites work: Maximum orbit weights in the \(\sigma \)-game and lit-only \(\sigma \)-game on grids and graphs
cites work: QUANTUM OCTAL GAMES
cites work: Q4944971
cites work: Chebyshev polynomials over finite fields and reversibility of \(\sigma\)-automata on square grids
cites work: Harmonic evolutions on graphs
cites work: More about singular line graphs of trees
cites work: Generalized switch-setting problems
cites work: Q5317419
cites work: Linear algebra approach to geometric graphs
cites work: Q4489185
cites work: On irreversibility of von Neumann additive cellular automata on grids
cites work: Linear cellular automata and the garden-of-eden
cites work: Q4799374
cites work: Minimum light number of lit-only \(\sigma\)-game on a tree
cites work: Even poset and a parity result for binary linear code
cites work: Periodic binary harmonic functions on lattices
DOI: 10.1016/J.EJC.2008.09.020
description: scientific article; zbMATH DE number 5565523