2025/03/14 by Bujtás, Csilla, Dokyeesun, Pakanun, Klavžar, Sandi +1 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics #G.2.1 #G.2.2
paper · doi:10.48550/arxiv.2503.11907
A predominated graph is a pair (G,D), where G is a graph and the vertices in D⊆ 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 ∪ \v\) for every vertex v ∈ V(G) ∖ 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 constructed.