The Solitaire Clobber game and correducibility

The Solitaire Clobber game is a one-player combinatorial game played on a graph. A stone, black or white, is placed on each vertex of the graph. A move in the game consists in picking up a stone and clobbering another one of different color located on an adjacent vertex; the clobbered stone is removed and replaced by the stone that has been moved. The game has been extensively investigated in relation to the problem of minimizing the number of stones remaining on the graph when no further move in the game is possible. We study a different question: for a given graph G, what is the largest positive integer k such that for every non-monochromatic configuration of stones on G and every subset S of V(G), there is a Solitaire Clobber game that empties S? We call this number the correducibility of G. For i=1,2, we show that a graph is i-correducible if and only if it is i-connected. Furthermore, for each k≥1, we prove that k-connected graphs are k-correducible. However, connectivity is a stronger condition on a graph than correducibility. Indeed, we give examples of graphs with small connectivity and arbitrary large correducibility.