论文标题
统治游戏中的3/5件注射的证明
A proof of the 3/5-conjecture in the domination game
论文作者
论文摘要
统治游戏是由Dominator和Staller的两个玩家玩的优化游戏，他们在图$ G $中选择了顶点。如果已选择或与选定的顶点相邻，则据说将其主导。每个选定的顶点在选择时必须严格增加主导的顶点的数量，并且一旦$ g $中的每个顶点占主导地位，游戏就结束了。 Dominator的目标是使游戏尽可能短，而Staller试图实现相反的目标。在本文中，我们证明，对于$ n $顶点上的任何图$ g $，Dominator具有最多最多3n/5 $移动的策略，这是由Kinnersley，West和Zamani猜想的。
The domination game is an optimization game played by two players, Dominator and Staller, who alternately select vertices in a graph $G$. A vertex is said to be dominated if it has been selected or is adjacent to a selected vertex. Each selected vertex must strictly increase the number of dominated vertices at the time of its selection, and the game ends once every vertex in $G$ is dominated. Dominator aims to keep the game as short as possible, while Staller tries to achieve the opposite. In this article, we prove that for any graph $G$ on $n$ vertices, Dominator has a strategy to end the game in at most $3n/5$ moves, which was conjectured by Kinnersley, West and Zamani.
