Criticality for Maker-Breaker domination games with predomination
Csilla Bujtás, Pakanun Dokyeesun, Sandi Klavžar, Miloš Stojaković · 2025
Read Criticality for Maker-Breaker domination games with predomination by Csilla Bujtás, Pakanun Dokyeesun, Sandi Klavžar, Miloš Stojaković (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-11907.txt.
Description
Csilla Bujtás and co-authors study a two-player domination game on graphs where some points start out already dominated, published in 2025. In the Maker-Breaker game, one player, Dominator, tries to dominate the whole graph. The other, Staller, tries to stop that outcome.
The authors define a critical form of such a setup. In it, Staller wins as given, but Dominator wins if any single extra point is added to the starting set. They build tools for the game on trees and characterize the critical trees. An algorithm checks in linear time whether a given tree is critical. They also present a large class of critical cactus graphs and build critical hypergraphs.
Catalog record
| CREATOR | Csilla Bujtás, Pakanun Dokyeesun, Sandi Klavžar, Miloš Stojaković |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-11907