Strong reducibility of powers of paths and powers of cycles on Impartial Solitaire Clobber

We consider the Impartial Solitaire Clobber which is a one-player combinatorial game on graphs. The problem of determining the minimum number of remaining stones after a sequence of moves was proved to be NP-hard for graphs in general and, in particular, for grid graphs. This problem was studied for paths, cycles and trees, and it was proved that, for any arrangement of stones, this number can be computed in polinomial time. We study a more complex question related to determining the color and the location of the remaining stones. A graph G is strongly 1-reducible if: for any vertex v of G, for any arrangement of stones on G such that G \ v is non-monochromatic, and for any color c, there exists a succession of moves that yields a single stone of color c on v. We investigate this problem for powers of paths P n r and for powers of cycles C n r and we prove that if r ⩾ 3 , then P n r (resp. C n r ) is strongly 1-reducible; if r = 2 , then P n r , is not strongly 1-reducible.