Analysis of ODD/ODD vertex removal games on special graphs
Independent thesis Advanced level (degree of Master (One Year)), 20 credits / 30 HE creditsStudent thesis
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.
IdentifiersURN: urn:nbn:se:kth:diva-102725OAI: oai:DiVA.org:kth-102725DiVA: diva2:556204
Master of Science in Engineering - Computer Science and Technology
Sjöstrand, Jonas, Univ lekt