The 4/5 upper bound on the game total domination number

The recently introduced total domination game is studied. This game is played on a graph G by two players, named Dominator and Staller. They alternately take turns choosing vertices of G such that each chosen vertex totally dominates at least one vertex not totally dominated by the vertices previously chosen. Dominator’s goal is to totally dominate the graph as fast as possible, and Staller wishes to delay the process as much as possible. The game total domination number, _γtg(G), of G is the number of vertices chosen when Dominator starts the game and both players play optimally. The Staller-start game total domination number, _γ′tg(G), of G is the number of vertices chosen when Staller starts the game and both players play optimally. In this paper it is proved that if G is a graph on n vertices in which every component contains at least three vertices, then _γtg(G)≤4n/5 and _γ′tg(G)≤(4n+2)/5. As a consequence of this result, we obtain upper bounds for both games played on any graph that has no isolated vertices.