A generalization of \textsc{Arc-Kayles}

DOI10.1007/S00182-018-0639-5MaRDI QIDQ2002065zbMATH OpenOpenAlexWikidataFDO

Authors Antoine Dailly, Valentin Gledel, Marc Heinrich

Publication date 11 July 2019

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

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

zbMATH Keywords

Arc-Kaylescombinatorial gamesgraphs

Mathematics Subject Classification ID

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

Abstract: The game Arc-Kayles is played on an undirected graph with two players taking turns deleting an edge and its endpoints from the graph. We study a generalization of this game, Weighted Arc Kayles (WAK for short), played on graphs with counters on the vertices. The two players alternate choosing an edge and removing one counter on both endpoints. An edge can no longer be selected if any of its endpoints has no counter left. The last player to play a move wins. We give a winning strategy for WAK on trees of depth 2. Moreover, we show that the Grundy values of WAK and Arc-Kayles are unbounded. We also prove a periodicity result on the outcome of WAK when the number of counters is fixed for all the vertices but one. Finally, we show links between this game and a variation of the non-attacking queens game on a chessboard.

Recommendations

• Polynomial time graph families for Arc Kayles
• scientific article; zbMATH DE number 512922
• scientific article; zbMATH DE number 7199604
• Kayles and Nimbers
• Exact algorithms for Kayles

Cites work

• A vertex and edge deletion game on graphs
• Combinatorial analysis of a subtraction game on graphs
• Combinatorial game theory
• scientific article; zbMATH DE number 3124339 (Why is no real title available?)
• scientific article; zbMATH DE number 5145315 (Why is no real title available?)
• scientific article; zbMATH DE number 3020856 (Why is no real title available?)
• Kayles and Nimbers
• On the complexity of some two-person perfect-information games
• Polynomial time graph families for Arc Kayles
• The computational complexity of the game of Set and its theoretical applications
• Winning ways for your mathematical plays. Vol. 1.

Cited in

(9)

• Art gallery problem with rook and queen vision
• Polynomial time graph families for Arc Kayles
• Kayles and Nimbers
• A codex of \(\mathcal{N}\)- and \(\mathcal{P}\)-positions in Harary's `caterpillar game'
• Lower and upper bounds for some generalized arcs
• Topological network-control games
• Topological network-control games
• Topological network-control games played on graphs
• Network control games played on graphs

This page was built for publication: A generalization of \textsc{Arc-Kayles}

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