Complexity of the game connected domination problemIršič Chenoweth, Vesna (Avtor) connected domination gamecomplexityPSPACE-completeThe connected domination game is a variant 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.20252025-10-06 10:17:41Članek v reviji174590sl