Analysis of ODD/ODD vertex removal games on special graphs
Institution: | KTH Royal Institute of Technology |
---|---|
Department: | |
Year: | 0 |
Keywords: | Master of Science in Engineering - Computer Science and Technology; Civilingenjörsexamen - Datateknik |
Record ID: | 1340888 |
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.