Article ID Journal Published Year Pages File Type
4654346 European Journal of Combinatorics 2009 14 Pages PDF
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 vv changes the state of all vertices in the open neighborhood of vv, while in the σ+σ+-game pushing vv 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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,