Game total domination for cycles and paths

Paul Dorbec, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

27 Citations (Scopus)


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 Cn on n ≥ 3 vertices, γtg(Cn)=⌊2n+1/3⌋-1 when n ≡ 4(mod6) and γtg(Cn)=⌊2n+1/3⌋ otherwise. Further, γtg'(Cn)=⌊2n/3⌋-1 when n ≡ 2(mod6) and γtg'(Cn)=⌊2n/3⌋ otherwise. For a path Pn on n ≥ 3 vertices, we show that γtg'(Pn)=⌈2n/3⌉. Further, γtg(Pn)=⌊2n/3⌋ when n ≡ 5(mod6) and ⌈2n/3⌉ otherwise.

Original languageEnglish
Pages (from-to)7-18
Number of pages12
JournalDiscrete Applied Mathematics
Publication statusPublished - 31 Jul 2016


  • Cycle
  • Domination game
  • Path
  • Total domination number

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Game total domination for cycles and paths'. Together they form a unique fingerprint.

Cite this