9
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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$
    – Mikhail Tikhomirov
    Sep 27, 2017 at 7:27

0

Reset to default

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.