The flipping puzzle on a graph

Hau wen Huang, Chih wen Weng

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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

Original languageEnglish
Pages (from-to)1567-1578
Number of pages12
JournalEuropean Journal of Combinatorics
Volume31
Issue number6
DOIs
StatePublished - Aug 2010

Fingerprint

Dive into the research topics of 'The flipping puzzle on a graph'. Together they form a unique fingerprint.

Cite this