Article ID Journal Published Year Pages File Type
4647190 Discrete Mathematics 2014 9 Pages PDF
Abstract

Solitaire Clobber   is a one-player combinatorial game on graphs. Each vertex of a graph GG starts with a black or a white stone. A stone on one vertex can clobber an adjacent stone of the opposite color, removing it and taking its place. The goal is to minimize the number of stones remaining when no further move is possible. An initial configuration is kk-reducible   if it can be reduced to kk stones. A graph is strongly 1-reducible   if, for any vertex vv, any initial configuration that is not monochromatic outside vv can be reduced to one stone, on vv, of either color. Every such graph has a Hamiltonian path ending at vv. For the path PnPn, we prove that the rrth distance power Pnr is strongly 1-reducible when r≥3r≥3 but not when r=2r=2 (Pn2 is 2-reducible). As a consequence, circulant graphs containing edges of lengths 1, 2, and 3 are strongly 1-reducible; we show also that those containing Cn2 are 1-reducible.

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