Criticality for Maker-Breaker domination games with predomination

Bujtás, Csilla (author), Dokyeesun, Pakanun (author), Klavžar, Sandi (author), Stojaković, Miloš (author)

A predominated graph is a pair $(G,D)$, where $G$ is a graph and the vertices in $D\subseteq V(G)$ are considered already dominated. Maker-Breaker domination game critical (MBD critical) predominated graphs are introduced as the predominated graphs $(G,D)$ on which Staller wins the game, but Dominator wins on $(G, D \cup \{v\})$ for every vertex $v \in V(G) \setminus D$. Tools are developed for handling the Maker-Breaker domination game on trees which lead to a characterization of Staller-win predominated trees. MBD critical predominated trees are characterized and an algorithm is designed which verifies in linear time whether a given predominated tree is MBD critical. A large class of MBD critical predominated cacti is presented and Maker-Breaker critical hypergraphs are constructed.

• Language: English
• Keywords: domination games, Maker-Breaker games, Maker-Breaker domination game, predomination, hypergraph
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Publication date: 01.01.2026
• Year: 2026
• Number of pages: Str. 483-506
• Numbering: Vol. 46, no. 2
• PID: 20.500.12556/RUL-181831
• UDC: 519.17
• ISSN on article: 1234-3099
• DOI: 10.7151/dmgt.2615
• COBISS.SI-ID: 275411971
• Publication date in RUL: 16.04.2026

Record is a part of a journal

• Title: Discussiones mathematicae : Graph theory
• Shortened title: Discuss. Math., Graph Theory
• Publisher: Technical University Press
• ISSN: 1234-3099
• COBISS.SI-ID: 7487065

Licences

• License: CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
• Link: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Description: The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.

Secondary language

• Language: Slovenian
• Keywords: dominacijske igre, igre izdelovalec-lomilec, dominacijska igra izdelovalec-lomilec, predominacija, hipergrafi