## Abstract

In this paper, we continue the study of the total domination game in graphs introduced in Henning et al. (2015) [10]. A vertex totally dominates another vertex in a graph G if they are neighbors. 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. The game ends when the set of vertices chosen becomes a total dominating set in G. Dominator wishes to end the game with a minimum number of vertices chosen, and Staller wishes to end the game with as many vertices chosen as possible. The game total domination number of G is the number of vertices chosen when Dominator starts the game and both players play optimally. In this paper, we show that verifying whether the game total domination number of a graph is bounded by a given integer is log-complete in PSPACE.

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

Pages (from-to) | 12-17 |

Number of pages | 6 |

Journal | Information Processing Letters |

Volume | 126 |

DOIs | |

Publication status | Published - Oct 2017 |

## Keywords

- Computational complexity
- POS-CNF problem
- PSPACE-complete problems
- Total domination game

## ASJC Scopus subject areas

- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications