Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4654346 | European Journal of Combinatorics | 2009 | 14 Pages |
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
John Goldwasser, Xinmao Wang, Yaokun Wu,