Trees with equal total domination and game total domination numbers

Michael A. Henning, Douglas F. Rall

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)

Abstract

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), (respectively, Staller-start game total domination number, γtg(G)) of G is the number of vertices chosen when Dominator (respectively, Staller) starts the game and both players play optimally. For general graphs G, sometimes γtg(G)>γtg(G). We show that if G is a forest with no isolated vertex, then γtg(G)≤γtg(G). Using this result, we characterize the trees with equal total domination and game total domination number.

Original languageEnglish
Pages (from-to)58-70
Number of pages13
JournalDiscrete Applied Mathematics
Volume226
DOIs
Publication statusPublished - 31 Jul 2017

Keywords

  • Game total domination number
  • Total domination game
  • Trees

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Trees with equal total domination and game total domination numbers'. Together they form a unique fingerprint.

Cite this