Does the lit-only restriction make any difference for the \(\sigma \)-game and \(\sigma ^+\)-game?
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.
scientific article; zbMATH DE number 5565523
scientific article