Complexity of the game connected domination problem

2024/04/12 by Chenoweth, Vesna Iršič
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2404.08776

Abstract

The connected domination game is a variation of the domination game where the played vertices must form a connected subgraph at all stages of the game. In this paper we prove that deciding whether the game connected domination number is smaller than a given integer is PSPACE-complete using log-space reductions for both Dominator- and Staller-start connected domination game.

Related

• Connected domination game: predomination, Staller-start game, and\n lexicographic products
• Complexity of the Game Domination Problem
• Predominating a vertex in the connected domination game
• Total connected domination game
• The Normal Play of the Domination Game