Abstract. The total domination game is a game played on a graph [Formula: see text] by 2 players, Dominator and Staller, who alternate in selecting vertices such that each newly selected vertex increases the number of vertices that are totally dominated by the set of selected vertices. The game stops when the set of selected vertices is a totally dominating set of [Formula: see text]. Dominator’s aim is to arrive at this state in as few moves as possible, while Staller wants to achieve the opposite. In this paper we prove the 3/4-conjecture by Henning, Klavžar, and Rall, stating that Dominator has a strategy for finishing the total domination game on [Formula: see text] within [Formula: see text] moves, where [Formula: see text] is the number of vertices of [Formula: see text]. We also prove that if the minimum degree of [Formula: see text] is at least 2, then Dominator can finish the game within [Formula: see text] moves.

The domination game is played on a graph G by two players, Dominator and Staller, who alternate in selecting vertices until each vertex in the graph G is contained in the closed neighbourhood of the set of selected vertices. Dominator’s aim is to reach this state in as few moves as possible, whereas Staller wants the game to last as long as possible. In this paper, we prove that if G has n vertices and minimum degree at least 2, then Dominator has a strategy to finish the domination game on G within 10n/17+1/17 moves, thus making progress towards a conjecture by Bujtás, Iršič and Klavžar.

We present an algorithm of time complexity O(knk+2) deciding whether a graph G on n vertices is k-copwin. The fastest algorithm thus far had time complexity O(n2k+2).