2015/12/09 by Henning, Michael A., Rall, Douglas F.
#05C65 #05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1512.02916
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), of G is the number of vertices chosen when Dominator starts the game and both players play optimally. Henning, Klavžar and Rall [Combinatorica, to appear] posted the (3)/(4)-Game Total Domination Conjecture that states that if G is a graph on n vertices in which every component contains at least three vertices, then γ\rm tg(G) ≤ (3)/(4)n. In this paper, we prove this conjecture over the class of graphs G that satisfy both the condition that the degree sum of adjacent vertices in G is at least 4 and the condition that no two vertices of degree 1 are at distance 4 apart in G. In particular, we prove that by adopting a greedy strategy, Dominator can complete the total domination game played in a graph with minimum degree at least 2 in at most 3n/4 moves.