Complexity of the game connected domination problem

DOI10.1016/J.TCS.2025.115559MaRDI QIDQ6896767zbMATH OpenFDO

Authors Vesna Iršič Chenoweth

Publication date 21 November 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115559

zbMATH Keywords

complexityconnected domination gamePSPACE-completeness

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43)

Cites work

• A connected version of the graph coloring game
• A note on the connected game coloring number
• A proof of the 3/4-conjecture for the total domination game
• A proof of the 3/5-conjecture in the domination game
• Complexity of the game domination problem
• Connected domination game
• Connected domination game played on Cartesian products
• Connected domination game: predomination, Staller-start game, and lexicographic products
• Domination game and an imagination strategy
• Domination games played on graphs
• Extremal problems for game domination number
• On the complexity of some two-person perfect-information games
• On the computational complexity of the domination game
• Predominating a vertex in the connected domination game
• Progress towards the 1/2-Conjecture for the domination game
• The connected greedy coloring game
• The game total domination problem is log-complete in PSPACE
• Total version of the domination game

This page was built for publication: Complexity of the game connected domination problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6896767)