کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418713 | 681712 | 2016 | 12 صفحه PDF | دانلود رایگان |
In this paper, we continue the study of the recently introduced total domination game in graphs. A vertex uu in a graph GG totally dominates a vertex vv if uu is adjacent to vv in GG. A total dominating set of GG is a set SS of vertices of GG such that every vertex of GG is totally dominated by a vertex in SS. The total domination game played on GG consists of two players, named Dominator and Staller, who alternately take turns choosing vertices of GG 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 GG 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 GG 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 GG is a cycle or a path. In particular, we show that for a cycle CnCn on n≥3n≥3 vertices, γtg(Cn)=⌊2n+13⌋−1 when n≡4(mod6) and γtg(Cn)=⌊2n+13⌋ otherwise. Further, γtg′(Cn)=⌊2n3⌋−1 when n≡2(mod6) and γtg′(Cn)=⌊2n3⌋ otherwise. For a path PnPn on n≥3n≥3 vertices, we show that γtg′(Pn)=⌈2n3⌉. Further, γtg(Pn)=⌊2n3⌋ when n≡5(mod6) and ⌈2n3⌉ otherwise.
Journal: Discrete Applied Mathematics - Volume 208, 31 July 2016, Pages 7–18