|Institution:||KTH Royal Institute of Technology|
|Keywords:||Master of Science in Engineering - Computer Science and Technology; Civilingenjörsexamen - Datateknik|
|Full text PDF:||http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-102725|
In this paper we analyze the odd/odd vertex removal game introduced by P. Ottaway. We prove that every bipartite graph has Grundy value 0 or 1 only depending on the parity of the number of edges in the graph. In addition we also reduce a conjecture proposed by K. Shelton to seemingly simpler one, in order to be able to show that there are graphs in the odd/odd vertex removal game for every possible Grundy value. Only the proof of the latter is incomplete and depends on this new conjecture.