Does the lit-only restriction make any difference for the \(\sigma \)-game and \(\sigma ^+\)-game? (Q1024268)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Does the lit-only restriction make any difference for the \(\sigma \)-game and \(\sigma ^+\)-game? |
scientific article |
Statements
Does the lit-only restriction make any difference for the \(\sigma \)-game and \(\sigma ^+\)-game? (English)
0 references
17 June 2009
0 references
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.
0 references
lit-only sigma game
0 references
reachability
0 references
configuration
0 references
toggle
0 references
line graph
0 references
orbit
0 references
0 references
0 references
0 references