An Achievement Game on a Cycle

2019/07/25 by Eero Räty, Raty, Eero
Computer Science · #05C57 #Advanced Graph Theory Research #Artificial Intelligence in Games #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.1907.11152

openalex publication_date 2019/07/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Consider the following game played by Maker and Breaker on the vertices of the cycle C_n, with first move given to Breaker. The aim of Maker is to maximise the number of adjacent pairs of vertices that are both claimed by her, and the aim of Breaker is to minimise this number. The aim of this paper is to find this number exactly for all n when both players play optimally, answering a related question of Dowden, Kang, Mikalački and Stojaković.

Related

• A Constructive Winning Maker Strategy in the Maker-Breaker C₄-Game
• On the Odd Cycle Game and Connected Rules
• Some Maker-Breaker games on hypergraphs
• A Strategy for Maker in the Clique Game which Helps to Tackle some Open Problems by Beck
• On the Constructor-Blocker Game