Chomp on generalized Kneser graphs and others

Ignacio García-Marco (), Kolja Knauer () and Luis Pedro Montejano ()
Additional contact information
Ignacio García-Marco: Universidad de La Laguna
Kolja Knauer: Université de Toulon, CNRS, LIS
Luis Pedro Montejano: CONACYT Research Fellow—Centro de Investigación en Matemáticas

International Journal of Game Theory, 2021, vol. 50, issue 3, No 2, 603-621

Abstract: Abstract In Chomp on graphs, two players alternatingly pick an edge or a vertex from a graph. The player that cannot move any more loses. The questions one wants to answer for a given graph are: Which player has a winning strategy? Can an explicit strategy be devised? We answer these questions (and determine the Nim-value) for the class of generalized Kneser graphs and for several families of Johnson graphs. We also generalize some of these results to the clique complexes of these graphs. Furthermore, we determine which player has a winning strategy for some classes of threshold graphs.

Keywords: Combinatorial games; Impartial games; Chomp; Generalized Kneser graphs; Johnson graphs; Threshold graphs; Clique complex; 05C57; 91A05; 91A46; 91A43; 91A05 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00182-019-00697-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jogath:v:50:y:2021:i:3:d:10.1007_s00182-019-00697-x

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

DOI: 10.1007/s00182-019-00697-x

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().