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 '17 at 4:00
  • $\begingroup$ @PyRulez: you are right of course, but this doesn't allow to answer any of the questions. $\endgroup$ – Mikhail Tikhomirov Sep 27 '17 at 7:27

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.