论文标题
笛卡尔产品的本地化游戏
The Localization Game On Cartesian Products
论文作者
论文摘要
本地化游戏是由两个玩家玩的：一个由$ k $警察组成的警察和一个强盗。该游戏是由强盗选择在V $中选择顶点$ r \的，这是警察未知的。此后，游戏将基于转弯。在每个回合开始时，COP探测$ K $的顶点，并在回报中收到距离向量。如果警察可以从矢量确定$ r $的确切位置，则强盗已找到并获胜。否则，允许强盗保持在$ r $，或者在$ r $的附近移至$ r'U $。然后，警察再次探测$ k $顶点。游戏以这种方式继续进行，如果强盗可以在有限的转弯处，警察将获胜。本地化编号$ζ（g）$被定义为最不正面的整数$ k $，而不论抢劫案的举动如何，警察都具有成功的策略。在本文中，我们专注于在笛卡尔产品上进行的游戏。我们证明$ζ（g \ quare H）\ geq \ max \ {ζ（g），ζ（h）\} $以及$ζ（g \ square h）\ leqζ（g） +ψ（g） +ψ（h）-1 $ where $ψ（h）$是$ h $ $ h $的doubly esolvane $。我们还表明$ζ（C_M \ Square C_N）$大多等于两个。
The localization game is played by two players: a Cop with a team of $k$ cops, and a Robber. The game is initialised by the Robber choosing a vertex $r \in V$, unknown to the Cop. Thereafter, the game proceeds turn based. At the start of each turn, the Cop probes $k$ vertices and in return receives a distance vector. If the Cop can determine the exact location of $r$ from the vector, the Robber is located and the Cop wins. Otherwise, the Robber is allowed to either stay at $r$, or move to $r'$ in the neighbourhood of $r$. The Cop then again probes $k$ vertices. The game continues in this fashion, where the Cop wins if the Robber can be located in a finite number of turns. The localization number $ζ(G)$, is defined as the least positive integer $k$ for which the Cop has a winning strategy irrespective of the moves of the Robber. In this paper, we focus on the game played on Cartesian products. We prove that $ζ( G \square H) \geq \max\{ζ(G), ζ(H)\}$ as well as $ζ(G \square H) \leq ζ(G) + ψ(H) - 1$ where $ψ(H)$ is a doubly resolving set of $H$. We also show that $ζ(C_m \square C_n)$ is mostly equal to two.
