Combinatorial Analysis of a Subtraction Game on GraphsReportar como inadecuado

Combinatorial Analysis of a Subtraction Game on Graphs - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

International Journal of Combinatorics - Volume 2016 2016, Article ID 1476359, 8 pages -

Research Article

Department of Mathematics, California State University, Fresno, Fresno, CA 93740, USA

Department of Mathematics, Kansas State University, Manhattan, KS 66506, USA

Clovis Community College, Fresno, CA 93730, USA

Received 14 April 2016; Revised 13 July 2016; Accepted 1 August 2016

Academic Editor: Laszlo A. Szekely

Copyright © 2016 Richard Adams et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


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.

Autor: Richard Adams, Janae Dixon, Jennifer Elder, Jamie Peabody, Oscar Vega, and Karen Willis



Documentos relacionados