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.
Best Answer
For an $n$-cycle, player 1 wins if $n$ is odd, else player 2 wins.
Since all vertices have degree 2, any vertex can have at most 1 token on it. Token-carrying vertices (of different colors) can be grouped into connected components. Call a component occupied by a player if it contains some vertex colored by the player, and that two components separated by a single vertex are adjacent. For example, the 6-cycle $(-*-1-2-*-1-*-)$ has 2 components, the first occupied by both players, the second occupied by player 1, and they are adjacent.
Lemma: If less than $n-2$ tokens have been played, it is player $i$'s turn to play, and player $i$ occupies a component, then she can ensure that she continues to occupy a component until her next turn.
To do so, she simply topples a component occupied by her. Toppling an occupied component results in two adjacent components occupied by her (you can see this by working out the result of toppling an isolated component). These may merge with adjacent neighbors of the original component, but this does not affect her occupancy. The opponent can in her turn topple at most one of these two components, leaving the other still occupied.
Neither player can lose before $n-2$ tokens have been played, if both follow the above strategy. On the $(n-2)$th play, any move results in a single $(n-1)$-vertex component. Suppose $n$ is even, so that it is player 1's turn, and player 2 on the previous turn created two distinct components occupied by her as above. Whether player 1 topples one of the components if she also occupies it, or joins the two by playing on an empty vertex, it leads to a single connected component occupied by player 2. Player 2 then wins by toppling the final component on the $n$th move. The same argument holds for Player 1 if $n$ is odd.
The strategy as such does not necessarily work for paths, because toppling a component adjacent to an end of the path does not create two separate components. My hunch is that for even $n$, starting from the middle then playing as above may still be a winning strategy for player 1, as it avoids the ends till the last turn. I don't know what the right strategy is for odd $n$, though experimentation leads me to believe player 2 should win.
I also can't see if there's any way to generalize this for general graphs, because it depends crucially on there being at most one token per vertex.