A Note on Lights-Out-Puzzle: Parity-State Graphs

College

College of Science

Department/Unit

Mathematics and Statistics Department

Document Type

Article

Source Title

Graphs and Combinatorics

Volume

27

Issue

1

First Page

109

Last Page

119

Publication Date

1-1-2011

Abstract

A state of a graph G is an assignment of 0 or 1 to each vertex of G. A move of a state consists of choosing a vertex and then switching the value of the vertex as well as those of its neighbors. Two states are said to be equivalent if one state can be changed to the other by a series of moves. A parity-state graph is defined to be a graph in which two states are equivalent if and only if the numbers of 1's in the two states have the same parity. We characterize parity-state graphs and present some constructions of parity-state graphs together with applications. Among other things, it is proved that the one-skeleton of the 3-polytope obtained from a simple 3-polytope by cutting off all vertices is a parity-state graph. © 2010 Springer.

html

Digitial Object Identifier (DOI)

10.1007/s00373-010-0958-1

Upload File

wf_yes

This document is currently not available here.

Share

COinS