AbstractsComputer Science

Analysis of ODD/ODD vertex removal games on special graphs

by Oliver Kruger




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


Abstract

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.