




















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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。