The recently introduced total domination game is studied. This game is played on a graph $G$ by two players, named Dominator and Staller. They alternately take turns choosing vertices of $G$ such that each chosen vertex totally dominates at least one vertex not totally dominated by the vertices previously chosen. Dominator's goal is to totally dominate the graph as fast as possible, and Staller wishes to delay the process as much as possible. The game total domination number, $\gamma_{tg}(G)$, of $G$ is the number of vertices chosen when Dominator starts the game and both players play optimally. The Staller-start game total domination number, $\gamma_{tg}'(G)$, of $G$ is the number of vertices chosen when Staller starts the game and both players play optimally. In this paper it is proved that if $G$ is a graph on $n$ vertices in which every component contains at least three vertices, then $\gamma_{tg}(G) \le 4n/5$ and $\gamma_{tg}'(G) \le (4n+2)/5$. As a consequence of this result, we obtain upper bounds for both games played on any graph that has no isolated vertices.
COBISS.SI-ID: 18018137
A longest sequence $S$ of distinct vertices of a graph $G$ such that each vertex of $S$ dominates some vertex that is not dominated by its preceding vertices, is called a Grundy dominating sequence; the length of $S$ is the Grundy domination number of $G$. In this paper we study the Grundy domination number in the four standard graph products: the Cartesian, the lexicographic, the direct, and the strong product. For each of the products we present a lower bound for the Grundy domination number which turns out to be exact for the lexicographic product and is conjectured to be exact for the strong product. In most of the cases exact Grundy domination numbers are determined for products of paths and/or cycles.
COBISS.SI-ID: 17829465
We continue the study of the Grundy domination number of a graph. A linear algorithm to determine the Grundy domination number of an interval graph is presented. The exact value of the Grundy domination number of an arbitrary Sierpiński graph is proven, and efficient algorithms to construct the corresponding sequences are presented. These results are obtained by using sharp bounds for the Grundy domination number of a vertex- and edge-removed graph, proven in this paper.
COBISS.SI-ID: 17807705
If $G$ is a graph, then a sequence $v_1,\dots,v_m$ of vertices is a closed neighborhood sequence if for all $2\le i \le m$ we have $N[v_i]\not\subseteq \cup_{j=1}^{i-1}N[v_j]$, and it is an open neighborhood sequence if for all $2\le i \le m$ we have $N(v_i)\not\subseteq \cup_{j=1}^{i-1}N(v_j)$. The length of a longest closed (open) neighborhood sequence is the Grundy (Grundy total) domination number of $G$. In this paper we introduce two similar concepts in which the requirement on the neighborhoods is changed to $N(v_i)\not\subseteq \cup_{j=1}^{i-1}N[v_j]$ or $N[v_i]\not\subseteq \cup_{j=1}^{i-1}N(v_j)$. In the former case we establish a strong connection to the zero forcing number of a graph, while we determine the complexity of the decision problem in the latter case. We also study the relationships among the four concepts, and discuss their computational complexities.
COBISS.SI-ID: 18163289
Two new techniques are introduced into the theory of the domination game. The cutting lemma bounds the game domination number of a partially dominated graph with the game domination number of a suitably modified partially dominated graph. The union lemma bounds the S-game domination number of a disjoint union of paths using appropriate weighting functions. Using these tools a conjecture asserting that the so-called three legged spiders are game domination critical graphs is proved. An extended cutting lemma is also derived and all game domination critical trees on 18, 19, and 20 vertices are listed.
COBISS.SI-ID: 18544729