20.500.12556/RUL-174590 Complexity of the game connected domination problem The 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. connected domination game complexity PSPACE-complete povezana dominacijska igra zahtevnost PSPACE-polno true false true Angleški jezik Slovenski jezik Članek v reviji 2025-10-06 10:17:41 2025-10-06 10:17:44 2026-06-30 13:57:41 0000-00-00 00:00:00 2025 0 0 11 str. art. 115559 Vol. 1057 Dec. 2025 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 0304-3975 10.1016/j.tcs.2025.115559 251830531 1-s2.0-S0304397525004979-main.pdf 1-s2.0-S0304397525004979-main.pdf 1 4A73BEDF1C906C36FEC9375F10038A3B dbcadb3ee2ce0348eb38974f4bff2b673966ba621b724c980c4cdba0c0c5bd8b 092f5944-a28d-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=219424 https://www.sciencedirect.com/science/article/pii/S0304397525004979 1 b5a1ff1d-a28c-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=219423 Fakulteta za matematiko in fiziko 0 0 0