Octal games on graphs: the game 0.33 on subdivided stars and bistars

DOI10.1016/J.TCS.2018.06.018MaRDI QIDQ1784739zbMATH OpenOpenAlexWikidataFDO

Authors Laurent Beaudou, Pierre Coupechoux, Antoine Dailly, Sylvain Gravier, Julien Moncel, Aline Parreau, Éric Sopena

Publication date 27 September 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

graphscombinatorial gamessubtraction gamesoctal games

Mathematics Subject Classification ID

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

Abstract: Octal games are a well-defined family of two-player games played on heaps of counters, in which the players remove alternately a certain number of counters from a heap, sometimes being allowed to split a heap into two nonempty heaps, until no counter can be removed anymore. We extend the definition of octal games to play them on graphs: heaps are replaced by connected components and counters by vertices. Thus, an octal game on a path P_n is equivalent to playing the same octal game on a heap of n counters. We study one of the simplest octal games, called 0.33, in which the players can remove one vertex or two adjacent vertices without disconnecting the graph. We study this game on trees and give a complete resolution of this game on subdivided stars and bistars.

Recommendations

• Combinatorial analysis of a subtraction game on graphs
• Connected subtraction games on subdivided stars
• Games without repetitions on trees and multitrees
• Edge deletion games with parity rules
• scientific article; zbMATH DE number 4181366

Cites work

• scientific article; zbMATH DE number 5145315 (Why is no real title available?)
• scientific article; zbMATH DE number 2115805 (Why is no real title available?)
• A deletion game on graphs: ``Le Pic Arête
• Combinatorial game theory
• Edge deletion games with parity rules
• Octal games on graphs: the game 0.33 on subdivided stars and bistars
• On the complexity of some two-person perfect-information games
• Superlinear period lengths in some subtraction games
• Undirected edge geography
• Vertex deletion games with parity rules

Cited in

(8)

• Daisies, Kayles, and the Sibert-Conway decomposition in misère octal games
• Connected subtraction games on subdivided stars
• Topological network-control games
• The game of Take Turn
• Power sum polynomials as relaxed EGZ polynomials
• Octal games on graphs: the game 0.33 on subdivided stars and bistars
• A vertex and edge deletion game on graphs
• Smash and grab: the \(0 \cdot 6\) scoring game on graphs

This page was built for publication: Octal games on graphs: the game 0.33 on subdivided stars and bistars

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