Maximum Orbit Weights in the σ-game and Lit-only σ-game on Grids and Graphs |
| |
Authors: | John L Goldwasser William F Klostermeyer |
| |
Institution: | (1) Department of Mathematics, West Virginia University, WV 26506 Morgantown, USA;(2) School of Computing, University of North Florida, FL 32224-2669 Jacksonville, USA |
| |
Abstract: | Let G be a graph in which each vertex can be in one of two states:
on or off. In the σ-game, when you “push” a vertex v you change the state of all of its neighbors, while in the σ+-game you change the state of v as well. Given a starting configuration of on vertices, the object of both games is to reduce it, by a sequence of pushes,
to the smallest possible number of on vertices. We show that any starting configuration in a graph with no isolated vertices
can, by a sequence of pushes, be reduced to at most half on, and we characterize those graphs for which you cannot do better.
The proofs use techniques from coding theory. In the lit-only versions of these two games, you can only push vertices which
are on. We obtain some results on the minimum number of on vertices one can obtain in grid graphs in the regular and lit-only
versions of both games. |
| |
Keywords: | Lights out σ -game maximum orbit weight |
本文献已被 SpringerLink 等数据库收录! |
|