|
|||||
 |
|
|
|
|
|
Lights Out on
finite graphs
Stephanie Edwards, Victoria Elandt, Nicholas James, Kathryn Johnson, Zachary Mitchell and Darin Stephenson
Vol. 3 (2010), No. 1, 17–32
|
Abstract |
|
Lights Out is a one-player game played on a finite graph. In the standard game the vertices can be either on or off; pressing a vertex toggles its state and that of all adjacent vertices. The goal of the game is to turn off all of the lights. We study an extension of the game in which the state of a vertex may be one of a finite number of colors. We determine which graphs in certain families (spider graphs and generalized theta graphs) are winnable for every initial coloring. We also provide a construction that gives every always-winnable tree for any prime power number of colors. |
Keywords
Lights Out, parity domination, finite graphs
|
Mathematical Subject Classification 2000
Primary: 05C15, 05C50, 05C78, 91A43
|
Milestones
Received: 13 April 2009
Revised: 21 December 2009
Accepted: 29 December 2009
Published: 20 April 2010
Communicated by Ron Gould
|
Authors |
| Stephanie Edwards | |
| Department of Mathematics Hope College Holland, MI 49423 United States |
|
| Victoria Elandt | |
| Department of Mathematical
Sciences University of Wisconsin Stevens Point, WI 54481-3897 United States |
|
| Nicholas James | |
| Department of Mathematics University of Florida Gainesville, FL 32611-8105 United States |
|
| Kathryn Johnson | |
| Department of Mathematics Hope College Holland, MI 49423 United States |
|
| Zachary Mitchell | |
| Department of Mathematics Hope College Holland, MI 49423 United States |
|
| Darin Stephenson | |
| Department of Mathematics Hope College Holland, MI 49423 United States |
|
|
