As part of the discussion on this question (Permutation Game Redux), a simple vertex-deletion game was proposed. The game is very simple.
Disconnect. Players alternately remove vertices from a graph $G$. The player that produces a fully disconnected graph (i.e., a graph with no edges) is the winner.
Because the game is impartial, the Sprague-Grundy theory applies: each game is equivalent to a nim-heap of some size (its nim-value), which can be calculated as the mex (minimum excluded nim-value) of its options. These nim-values can then be used to compute the nim-values of disjunctive sums of games in the usual way.
One would like to apply this theory within a single game, e.g., to break a graph into its connected components, calculate their nim-values, and then combine them to find the value of the overall graph. Unfortunately, this doesn't work. The problem is that the win condition is not standard: the game ends before all moves are exhausted (or, equivalently, the allowed moves in one component of the graph depend on the other components).
It is not hard to see that for any graph $G$ and any even $n$, the game $G \cup \bar{K}_n$ is equivalent to $G$ (where $\bar{K}_n$ is the edgeless graph on $n$ vertices). To prove it, we need to show that the disjunctive sum $G + G\cup\bar{K}_n$ is a second-player win. The proof is by induction on $|G|+n$. If $G$ is edgeless, then the first player loses immediately (both games are over). Otherwise, the first player can move in either $G$, and the second player can copy his move in the other one (reducing to $G' + G'\cup \bar{K_n}$ with $|G'|=|G|-1$); or, if $n\ge 2$, the first player can move in the disconnected piece, and the second player can do the same (reducing to $G + G\cup\bar{K}_{n-2}$).
This shows that any graph $G$ is equivalent to $H \cup K_p$, where $H$ is the part of $G$ with no disconnected vertices, and $p=0$ or $1$ is the parity of the number of disconnected vertices in $G$. All games in an equivalence class have the same nim-value, and moreover, the equivalence relation respects the union operation: if $G \sim H \cup K_p$ and $G' \sim H' \cup K_{p'}$ then $G \cup G' \sim (H \cup H')\cup K_{p\oplus p'}$. Moreover, one can see that the games in $[H \cup K_0]$ and $[H \cup K_1]$ have different nim-values unless $H$ is the null graph: when playing $H + H \cup K_1$, the first player can take the isolated vertex, leaving $H+H$, and then copy the second player's moves thereafter.
Beyond this, are there any other general decomposition or equivalence results? Any extension of the Sprague-Grundy theory to this class of games? In particular, is there some more refined equivalence relation still to be found such that all games in $[G]$ have the same nim-value, and $[G \cup H]$ can be determined in terms of $[G]$ and $[H]$?
