Notes on the combinatorial game: graph Nim

Richard M. Low (Dept. of Mathematics San Jose State University, USA)
W.H. Chan (Dept. of Mathematics and Information Technology, The Hong Kong Institute of Education, Hong Kong)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 4, No 2 (2016): Electronic Journal of Graph Theory and Applications

The combinatorial game of Nim can be played on graphs. Over the years, various Nim-like games on graphs have been proposed and studied by N.J. Calkin et al., L.A. Erickson and M. Fukuyama. In this paper, we focus on the version of Nim played on graphs which was introduced by N.J. Calkin et al.: Two players alternate turns, each time choosing a vertex $v$ of a finite graph and removing any number $(\geq 1)$ of edges incident to $v$. The player who cannot make a move loses the game. Here, we analyze Graph Nim for various classes of graphs and also compute some Grundy-values.