Preskoči na glavno vsebino

Pakanun Dokyeesun: Maker-Breaker domination game on Cartesian products of complete bipartite graphs

Datum objave: 27. 11. 2023
Seminar za diskretno matematiko
Plemljev seminar, Jadranska 19


The Maker-Breaker domination game is played on a graph G by two players, called Dominator and Staller. They alternately select an unplayed vertex in G. Dominator wins the game if he forms a dominating set while Staller wins the game if she claims all vertices from a closed neighborhood of a vertex. If Dominator is the winner in the D-game (or the S-game), then γMB (G)  (or γ'MB(G) ) is defined by the minimum number of moves of Dominator to win the game under any strategy of Staller. Analogously, when Staller is the winner, γSMB(G) and γ'SMB(G) can be defined in the same way. In this talk, we establish the winner in the D-game and the S-game on Km,n □ Km',n' for every positive integers m, m',n,n'. The exact formulas for  γMB (G), γ'MB(G), γSMB(G) and γ'SMB(G) are also proved where G is a product of stars.