On the game total domination number

Abstract

The total domination game is a two-person competitive optimization game, where the players, Dominator and Staller, alternately select vertices of an isolate-free graph $G$. Each vertex chosen must strictly increase the number of vertices totally dominated. This process eventually produces a total dominating set of $G$. Dominator wishes to minimize the number of vertices chosen in the game, while Staller wishes to maximize it. The game total domination number of $G$, ${\gamma }_{\mathrm{tg}}(G)$, is the number of vertices chosen when Dominator starts the game and both players play optimally. Recently, Henning, Klavžar, and Rall proved that ${\gamma }_{\mathrm{tg}}(G)\le \frac{4}{5}n$ holds for every graph $G$ which is given on $n$ vertices such that every component of it is of order at least $3$; they also conjectured that the sharp upper bound would be $\frac{3}{4}n$. Here, we prove that ${\gamma }_{\mathrm{tg}}(G)\le \frac{11}{14}n$ holds for every $G$ which contains no isolated vertices or isolated edges.

11 pages