2022/12/08 by Leo Versteegen, Versteegen, Leo · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2212.04527
openalex publication_date 2022/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The domination game is an optimization game played by two players, Dominator and Staller, who alternately select vertices in a graph G. A vertex is said to be dominated if it has been selected or is adjacent to a selected vertex. Each selected vertex must strictly increase the number of dominated vertices at the time of its selection, and the game ends once every vertex in G is dominated. Dominator aims to keep the game as short as possible, while Staller tries to achieve the opposite. In this article, we prove that for any graph G on n vertices, Dominator has a strategy to end the game in at most 3n/5 moves, which was conjectured by Kinnersley, West and Zamani.