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

DOI10.1016/J.TCS.2018.06.018zbMATH Open1418.91098arXiv1612.05772OpenAlexW2567188812WikidataQ129376356 ScholiaQ129376356MaRDI QIDQ1784739FDOQ1784739

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)

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.

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

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

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)

Cites Work

• Combinatorial game theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the complexity of some two-person perfect-information games
• Undirected edge geography
• Vertex deletion games with parity rules
• Superlinear period lengths in some subtraction games
• Octal games on graphs: the game 0.33 on subdivided stars and bistars
• A deletion game on graphs: ``Le Pic Arête
• Edge 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)