A deletion game on hypergraphs

DOI10.1016/0166-218X(91)90041-TMaRDI QIDQ805510zbMATH OpenOpenAlexFDO

Authors Aviezri S. Fraenkel, Edward Scheinerman

Publication date 1991

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(91)90041-t

zbMATH Keywords

complete multipartite graphscycleshypergraphNimP-partiteP-uniformSprague-Grundy function

Mathematics Subject Classification ID

Hypergraphs (05C65) 2-person games (91A05) Games involving graphs (91A43)

Review text

Let H be a finite, simple hypergraph and \(\Gamma\) (H) be the game in which players alternately delete either a vertex or an edge (with all vertices contained in the edge). As in Nim, the first player unable to move loses. The authors solve \(\Gamma\) (H) when H is a disjoint union of hypergraphs which are (1) P-uniform, P-partite; (2) cycles; and (3) complete multipartite graphs.

Recommendations

• Impartial hypergraph games
• scientific article; zbMATH DE number 6438474
• A vertex and edge deletion game on graphs
• Sprague-Grundy function of symmetric hypergraphs
• Sprague-Grundy function of matroids and related hypergraphs

Cites work

• A complete analysis of von Neumann's Hackendot
• A Curious Nim-Type Game
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3761989 (Why is no real title available?)
• Nim-type games

Cited in

(16)

• Games without repetitions on trees and multitrees
• Recent results and questions in combinatorial game complexities
• Complexity, appeal and challenges of combinatorial games
• Combinatorial analysis of a subtraction game on graphs
• Vertex deletion games with parity rules
• A deletion game on graphs: ``Le Pic Arête
• Around Wythoff's game
• scientific article; zbMATH DE number 1906344 (Why is no real title available?)
• A codex of \(\mathcal{N}\)- and \(\mathcal{P}\)-positions in Harary's `caterpillar game'
• The complexity of poset games
• A vertex and edge deletion game on graphs
• Edge deletion games with parity rules
• Delete nim
• Impartial hypergraph games
• Edge-removing games on graphs
• Bart--Moe games, JumbleG and discrepancy

This page was built for publication: A deletion game on hypergraphs

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