Chomp on generalized Kneser graphs and others

DOI10.1007/S00182-019-00697-XzbMATH Open1473.05204arXiv1803.03081OpenAlexW2981817218WikidataQ126975915 ScholiaQ126975915MaRDI QIDQ2230537FDOQ2230537

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)

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.

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

Recommendations

• On three-rowed chomp
• scientific article
• A Nim game played on graphs.
• A Nim game played on graphs. II.
• Nim on the complete graph.

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)

Cites Work

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

Cited In (3)

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

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)