Article ID Journal Published Year Pages File Type
4654266 European Journal of Combinatorics 2010 12 Pages PDF
Abstract

Let SS be a connected graph which contains an induced path of n−1n−1 vertices, where nn is the order of SS. We consider a puzzle on SS. A configuration of the puzzle is simply an nn-dimensional column vector over {0,1}{0,1} with coordinates of the vector indexed by the vertex set SS. For each configuration uu with a coordinate us=1us=1, there exists a move that sends uu to the new configuration which flips the entries of the coordinates adjacent to ss in uu. We completely determine if one configuration can move to another in a sequence of finite steps.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,