标题： 博弈支配问题的复杂性 显示英文标题

标题： Complexity of the Game Domination Problem

摘要： 游戏支配数是一个图不变量，它来源于一个游戏，其与图支配的关系类似于游戏着色数与图着色的关系。 在本文中我们证明，验证图的游戏支配数是否被给定整数所限制是PSPACE完全的。 这与游戏着色问题的情况形成对比，该游戏着色问题的复杂性仍然未知。 显示英文摘要

摘要： The game domination number is a graph invariant that arises from a game, which is related to graph domination in a similar way as the game chromatic number is related to graph coloring. In this paper we show that verifying whether the game domination number of a graph is bounded by a given integer is PSPACE-complete. This contrasts the situation of the game coloring problem whose complexity is still unknown.