10 papers
On the damage number of graphs
Valentin Gledel, William B. Kinnersley, Balázs Patkós +1
We study a variant of Cops and Robbers in which the robber attempts to visit as many vertices of the graph as possible without being captured, while the cop aims to keep the robber…
Patrolling cop vs omniscient robber
Nina Chiarelli, Paul Dorbec, MiloÅ¡ StojakoviÄ +1
We study a variant of the classical Cops and Robbers game with one cop and one robber. The cop follows a fixed walk on the graph, called a patrol, that is chosen before the game be…
On the Multi-Robber Damage Number
MiloÅ¡ StojakoviÄ, Lasse Wulf
We study a variant of the Cops and Robbers game on graphs in which the robbers damage the visited vertices, aiming to maximize the number of damaged vertices. For that game with on…
The Nesting Bird Box Problem is ER-complete: Sharp Hardness Results for the Hidden Set Problem
Lucas Meijer, Till Miltzow, Johanna Ockenfels +1
In the (Nesting) Bird Box Problem we are given a polygonal domain P and a number k and we want to know if there is a set B of k points inside P such that no two points in B can see…
Rainbow connectivity Maker-Breaker game
Juri Barkey, Bruno Borchardt, Dennis Clemens +3
We study biased Maker-Breaker games on a graph system , in which Maker's goal is to claim certain rainbow structures, i.e., specified subgraphs consisting of at…
Positional s-of-k games
Eric Duchêne, Valentin Gledel, MiloÅ¡ StojakoviÄ
We introduce a general framework for positional games in which players score points by claiming a prescribed portion of each winning set, extending the notion of scoring Maker-Brea…