Vol. 3, No. 1, 2010

Download this article
Download this article For screen
For printing
Recent Issues

Volume 11, 1 issue

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
Cover Page
Editorial Board
Editors’ Addresses
Editors’ Interests
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Subscriptions
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
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