Progress towards the total domination game -conjecture
Progress towards the total domination game -conjecture
复制标题
DOI：
10.1016/j.disc.2016.05.014
复制
发表时间：
2016-11
期刊：
影响因子：
--
通讯作者：
Michael A. Henning;Douglas F. Rall
中科院分区：
文献类型：
--
作者：
Michael A. Henning;Douglas F. Rall
In this paper, we continue the study of the total domination game in graphs introduced in Henning et al.(2015), 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, γ tg (G), of G is the number of vertices chosen when Dominator starts the game and both players play optimally. Henning et al.(in press) 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 γ 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 3 n/4 moves.
