Computing Lopez type and $∗$-type for Lopez graph games. These graph games were first ideated by Carlos Lopez.

GitHub Repository

Readme Card

Last Commit GitHub Stars

👉 View the full repository on GitHub

Mathematical Setting

A Lopez graph game is a game held between two players on a given, undirected graph $G = (V, E)$. Players alternate making moves on $G$ and its resulting subgraphs until a winner is determined. A move is defined as a player removing either:

  • A single vertex $v \in V$ (and all edges $e \in E$ with $v \in e$), or
  • Two adjacent vertices $u, v$ (and all edges $e \in E$ with $u \in e \lor v \in e$).
  • The resulting $G’ = (V’, E’)$ is the subgraph of $G$ on which the next player must play.
  • In the normal version of the Lopez graph game, the last player to remove a vertex wins.
  • In the adjoint version (or $*$ version) of the Lopez graph game, the last player to remove a vertex loses.
  • In the normal (or adjoint) version,
    • if Player I can guarantee a win no matter Player II’s responses, we say that the graph $G$ on which they started play has Lopez type I (or Lopez $\ast$-type I$^{*}$, resp.).
    • Otherwise, we say that $G$ has Lopez type II (or Lopez $\ast$-type II$^{*}$, resp.).