• Title of article

    Does the lit-only restriction make any difference for the -game and -game?

  • Author/Authors

    Goldwasser، نويسنده , , John and Wang، نويسنده , , Xinmao and Wu، نويسنده , , Yaokun، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2009
  • Pages
    14
  • From page
    774
  • To page
    787
  • Abstract
    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 σ -game, “pushing” a vertex v changes the state of all vertices in the open neighborhood of v , while in the σ + -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. We consider the lit-only restriction on these two games where a vertex can be pushed only if it is in the on state. We show that the lit-only restriction can make a big difference for reachability in the σ -game, but has essentially no effect in the σ + -game.
  • Journal title
    European Journal of Combinatorics
  • Serial Year
    2009
  • Journal title
    European Journal of Combinatorics
  • Record number

    1548281