Let $G = (V, E)$ be a finite graph, and $S \subseteq V$ initially be an empty set. Alice and Bob play a game, making moves in turns starting with Alice. A move consists of choosing a vertex $v \in V \backslash S$ such that $v$ is not adjacent to any vertex of $S$, and adding $v$ to $S$. The player without any valid move options loses.

Consider the class $\mathcal{G_A}$ of graphs for which Alice has a winning strategy. Is there a (feasible) combinatorial graph invariant that is equivalent to membership in $\mathcal{G_A}$? What is the complexity of deciding membership in $\mathcal{G_A}$? Are these questions simpler if we restrict $G$ to be a tree?

  • 1
    $\begingroup$ Consider the game as starting with $V$, and removing vertices (along with their neighbors). Than this game can naturally be analyzed using nimbers, since when our graph becomes disconnected, it is essentially a nimber sum. $\endgroup$
    – PyRulez
    Sep 27, 2017 at 4:00
  • $\begingroup$ @PyRulez: you are right of course, but this doesn't allow to answer any of the questions. $\endgroup$ Sep 27, 2017 at 7:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.