2016/09/10 by Henning, Michael A., Rall, Douglas F.
#05C65 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1609.03059
In this paper, we continue the study of the total domination game in graphs introduced in [Graphs Combin. 31(5) (2015), 1453--1462], where the players Dominator and Staller alternately select vertices of G. Each vertex chosen must strictly increase the number of vertices totally dominated, where a vertex totally dominates another vertex if they are neighbors. This process eventually produces a total dominating set S of G in which every vertex is totally dominated by a vertex in S. Dominator wishes to minimize the number of vertices chosen, while Staller wishes to maximize it. The game total domination number, γ\rm tg(G), (respectively, Staller-start game total domination number, γ\rm tg'(G)) of G is the number of vertices chosen when Dominator (respectively, Staller) starts the game and both players play optimally. For general graphs G, sometimes γ\rm tg(G) > γ\rm tg'(G). We show that if G is a forest with no isolated vertex, then γ\rm tg(G) ≤ γ\rm tg'(G). Using this result, we characterize the trees with equal total domination and game total domination number.