Solitaire clobber on circulant graphs

Solitaire Clobber is a one-player combinatorial game on graphs. Each vertex of a graph G 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 k -reducible if it can be reduced to k stones. A graph is strongly 1-reducible if, for any vertex v , any initial configuration that is not monochromatic outside v can be reduced to one stone, on v , of either color. Every such graph has a Hamiltonian path ending at v . For the path P n , we prove that the r th distance power P n r is strongly 1-reducible when r ≥ 3 but not when r = 2 ( P n 2 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 C n 2 are 1-reducible.