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
    0 references
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers