## Abstract

In this paper, we continue the study of the recently introduced total domination game in graphs. A vertex u in a graph G totally dominates a vertex v if u is adjacent to v in G. A total dominating set of G is a set S of vertices of G such that every vertex of G is totally dominated by a vertex in S. The total domination game played on G consists of two players, named Dominator and Staller, who 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, γ_{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, γ_{tg}'(G), of G is the number of vertices chosen when Staller starts the game and both players play optimally. In this paper we determine γ_{tg}(G) and γ_{tg}'(G) when G is a cycle or a path. In particular, we show that for a cycle C_{n} on n ≥ 3 vertices, γ_{tg}(C_{n})=⌊2n+1/3⌋-1 when n ≡ 4(mod6) and γ_{tg}(C_{n})=⌊2n+1/3⌋ otherwise. Further, γ_{tg}'(C_{n})=⌊2n/3⌋-1 when n ≡ 2(mod6) and γ_{tg}'(C_{n})=⌊2n/3⌋ otherwise. For a path P_{n} on n ≥ 3 vertices, we show that γ_{tg}'(P_{n})=⌈2n/3⌉. Further, γ_{tg}(P_{n})=⌊2n/3⌋ when n ≡ 5(mod6) and ⌈2n/3⌉ otherwise.

Original language | English |
---|---|

Pages (from-to) | 7-18 |

Number of pages | 12 |

Journal | Discrete Applied Mathematics |

Volume | 208 |

DOIs | |

Publication status | Published - 31 Jul 2016 |

## Keywords

- Cycle
- Domination game
- Path
- Total domination number

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics