Given a connected graph $G$, two players, Blue and Green, play the following game: initially, all vertices are unclaimed. Players alternate turns. On her turn, Blue adds a token to either an unclaimed vertex (turning it blue) or a blue vertex, and similarly on his turn, Green adds a token to either an unclaimed vertex (turning it green) or a green vertex.

If a vertex of degree $d$ ever receives $d$ tokens, it *topples*, donating one token to each of its neighbors. This may in turn cause some of its neighbors to topple, and so on, as in the sandpile model. If Blue sets off a sequence of one or more topplings, she colors blue every vertex on which a token landed as a consequence of her move, and likewise for Green. (Note that because the sandpile model is abelian, we don't need to specify an order of topplings.) A player wins when she has managed to color the entire graph in her color.

**Question**: For which graphs $G$ is this game a first-player win?

I would be interested in any nontrivial statements for interesting classes of graphs, e.g., for paths, trees, cycles, complete bipartite graphs, grid graphs, whatever. The game is trivially a first-player win on a complete graph $K_n$: the first player simply plays $n - 1$ times on the same vertex, and there is nothing the second player can do. It's also not hard to see that it's a second-player win on the graph with two edges and three vertices: the first player cannot win on her move, and following her move there is always one token on the degree-2 vertex. The second player places a token on the unclaimed leaf vertex, which topples; there are now two tokens on the degree-2 vertex, which topples, making player 2 the winner.

*Motivation*: This came up not in my research but rather in my relaxation -- there's a game installed on my math department Linux distribution called KJumpingCube, which is precisely this game on square grid graphs.

One could also ask the same question for directed graphs, of course.

7more comments