Gamburgers and Graphs with Small Game Domination Number

Simon Schmidt
Joseph Fourier's University Grenoble

Sandi Klav\v{z}ar
Faculty of Mathematics and Physics, University of Ljubljana

Ga\v{s}per Ko\v{s}mrlj
Abelium, R\&D d.o.o., Ljubljana



Content: The domination game is played on a graph $G$ by Dominator and Staller. The two players are taking turns choosing a vertex from $G$ such that at least one previously undominated vertex becomes dominated. Dominator wants to finish the game as fast as possible, while Staller wants to prolong it. The game is called D-game, when Dominator starts and S-game otherwise. The game domination number $\gamma_g(G)$ of $G$ is the number of moves played in D-game when both players play optimally. Similarly, $\gamma_g'(G)$ is the number of moves played in S-Game. In this talk, graphs $G$ with $\gamma_g(G)=2$ and graphs with $\gamma_g'(G)=2$, as well as graphs extremal with respect to the diameter among these graphs are characterized. In particular, $\gamma_g'(G) = 2$ and ${\rm diam}(G) = 3$ hold for a graph $G$ if and only if $G$ is a so-called gamburger. The classes of graphs with $\gamma_g=3$ or $\gamma_g'=3$ turn to be much richer. Though, we are able to characterize graphs $G$ with $\gamma_g(G) = 3$ and ${\rm diam}(G) = 6$, as well as graphs $G$ with $\gamma_g'(G) = 3$ and ${\rm diam}(G) = 5$. The latter can be described as the so-called double-gamburgers.

Back to all abstracts