The constructor-blocker game

Patkós, Balázs and Stojakovic, Milos and Vizer, Máté (2024) The constructor-blocker game. APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS, Online. ISSN 1452-8630

Preview

Text 2203.14707v4.pdf Available under License Creative Commons Attribution. Download (255kB) | Preview

Abstract

We study the following game version of generalized graph Turán problems. For two fixed graphs F and H, two players, Constructor and Blocker, alternately claim unclaimed edges of the complete graph Kn. Constructor can only claim edges so that he never claims all edges of any copy of F , i.e. his graph must remain F -free, while Blocker can claim unclaimed edges without restrictions. The game ends when Constructor cannot claim further edges or when all edges have been claimed. The score of the game is the number of copies of H with all edges claimed by Constructor. Constructor’s aim is to maximize the score, while Blocker tries to keep the score as low as possible. We denote by g(n, H, F ) the score of the game when both players play optimally and Constructor starts the game. In this paper, we obtain the exact value of g(n, H, F ) when both F and H are stars and when F = P4, H = P3. We determine the asymptotics of g(n, H, F ) when F is a star and H is a tree and when F = P5, H = K3, and we derive upper and lower bounds on g(n, P4, P5).

Actions (login required)

Edit Item