Criticality for Maker-Breaker domination games with predomination

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

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.

• Jezik: Angleški jezik
• Ključne besede: domination games, Maker-Breaker games, Maker-Breaker domination game, predomination, hypergraph
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Datum objave: 01.01.2026
• Leto izida: 2026
• Št. strani: Str. 483-506
• Številčenje: Vol. 46, no. 2
• PID: 20.500.12556/RUL-181831
• UDK: 519.17
• ISSN pri članku: 1234-3099
• DOI: 10.7151/dmgt.2615
• COBISS.SI-ID: 275411971
• Datum objave v RUL: 16.04.2026

Gradivo je del revije

• Naslov: Discussiones mathematicae : Graph theory
• Skrajšan naslov: Discuss. Math., Graph Theory
• Založnik: Technical University Press
• ISSN: 1234-3099
• COBISS.SI-ID: 7487065

Licence

• Licenca: CC BY-NC-ND 4.0, Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by-nc-nd/4.0/deed.sl
• Opis: Najbolj omejujoča licenca Creative Commons. Uporabniki lahko prenesejo in delijo delo v nekomercialne namene in ga ne smejo uporabiti za nobene druge namene.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: dominacijske igre, igre izdelovalec-lomilec, dominacijska igra izdelovalec-lomilec, predominacija, hipergrafi