Combinatorial Analysis of a Subtraction Game on Graphs. (29th August 2016)

• Record Type: Journal Article
• Authors: Adams, Richard; Dixon, Janae; Elder, Jennifer; Peabody, Jamie; Vega, Oscar; Willis, Karen
• Other Names: Szekely Laszlo A. Academic Editor.
• Is Part Of: International journal of combinatorics. Volume 2016(2016)
• Publication Date: 2016-08-29
• Subjects: Combinatorial analysis -- Periodicals; Combinatorial analysis; Periodicals; Electronic journals; 511.605
• DOI: 10.1155/2016/1476359
• Languages: English
• ISSNs: 1687-9163

Abstract

Abstract : We define a two-player combinatorial game in which players take alternate turns; each turn consists of deleting a vertex of a graph, together with all the edges containing such vertex. If any vertex became isolated by a player's move then it would also be deleted. A player wins the game when the other player has no moves available. We study this game under various viewpoints: by finding specific strategies for certain families of graphs, through using properties of a graph's automorphism group, by writing a program to look at Sprague-Grundy numbers, and by studying the game when played on random graphs. When analyzing Grim played on paths, using the Sprague-Grundy function, we find a connection to a standing open question about Octal games.