Chomp on generalized Kneser graphs and others

DOI10.1007/S00182-019-00697-XMaRDI QIDQ2230537zbMATH OpenOpenAlexWikidataFDO

Authors Ignacio García Marco, Kolja Knauer, Luis Pedro Montejano

Publication date 24 September 2021

Published in International Journal of Game Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.03081

zbMATH Keywords

combinatorial gamesJohnson graphsthreshold graphsclique compleximpartial gamesgeneralized Kneser graphschomp

Mathematics Subject Classification ID

2-person games (91A05) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Combinatorial games (91A46)

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 a 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.

Recommendations

• On three-rowed chomp
• scientific article; zbMATH DE number 4181366
• A Nim game played on graphs.
• A Nim game played on graphs. II.
• Nim on the complete graph.

Cites work

• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 7075886 (Why is no real title available?)
• A Curious Nim-Type Game
• Automorphisms and regular embeddings of merged Johnson graphs
• Chomp on numerical semigroups
• Counterexamples to conjectures about subset takeaway and counting linear extensions of a Boolean lattice
• David Gale's Subset Take-Away Game
• Nim-type games
• Winning ways for your mathematical plays. Vol. 1.
• Zermelo and the early history of game theory

Cited in

(3)

• Chomp on numerical semigroups
• A vertex and edge deletion game on graphs
• Kneser graphs are Hamiltonian

This page was built for publication: Chomp on generalized Kneser graphs and others

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2230537)