Search

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. [ABSTRACT FROM AUTHOR]

The domination game played on a graph G consists of two players, Dominator and Staller, who alternate taking turns choosing a vertex from G such that whenever a vertex is chosen by either player, at least one additional vertex is dominated. Dominator wishes to dominate the graph in as few steps as possible, and Staller wishes to delay the process as much as possible. The game domination number γg (G) (resp., γ'g(G)) is the number of vertices chosen when Dominator (resp., Staller) starts the game. An imagination strategy is developed as a general tool for proving results Oil the domination game. We show that for any graph G, γ(G) ≤ γg(G)≤ 2γ(G) - 1, and that all possible values can be realized. It is proved that for any graph G, γg(G) - 1 ≤γ'g(G) ≤ γg (G) + 2, and that most of the possibilities for mutual values of γg(G) and γ'g(G) can be realized. A connection with Vizing's conjecture is established, and a lower bound on the game domination number of an arbitrary Cartesian product is proved. Several problems and conjectures are also stated. [ABSTRACT FROM AUTHOR]

We introduce a new setting for dealing with the problem of the domination number of the Cartesian product of graphs related to Vizing's conjecture. The new framework unifies two different approaches to the conjecture. The most common approach restricts one of the factors of the product to some class of graphs and proves the inequality of the conjecture then holds when the other factor is any graph. The other approach utilizes the so-called Clark-Suen partition for proving a weaker inequality that holds for all pairs of graphs. We demonstrate the strength of our framework by improving the bound of Clark and Suen as follows: γ(X□Y) ≥ max {1/2γ (X)γt(Y), 1/2γt(X)γ(Y)}, where γ stands for the domination number, γt is the total domination number, and X □ Y is the Cartesian product of graphs X and Y [ABSTRACT FROM AUTHOR]