标题： 树和外平面图的定位游戏捕获时间 显示英文标题

标题： Localization game capture time of trees and outerplanar graphs

摘要： 定位游戏是警匪游戏的一种变体，其中匪徒是不可见的，并在相邻顶点之间移动，但警察能够探测图中的任何$k$个顶点，以获得探测顶点和匪徒之间的距离。 图的定位数是在有限时间内让警察找到匪徒所需的最小$k$。 定位捕获时间是警察获胜所需的轮数。 定位捕获时间猜想认为存在一个常数$C$，使得每个具有$n$个顶点的连通图的定位数最多为$Cn$。 虽然已知该猜想对树成立，但在本文中我们显著改进了树的定位捕获时间的已知上界。 我们还证明了外平面图的一个子类的猜想，并提出了一个定位游戏的推广形式，这似乎有助于进一步推进该猜想的研究。 显示英文摘要

摘要： The localization game is a variant of the game of Cops and Robber in which the robber is invisible and moves between adjacent vertices, but the cops can probe any $k$ vertices of the graph to obtain the distance between probed vertices and the robber. The localization number of a graph is the minimum $k$ needed for cops to be able to locate the robber in finite time. The localization capture time is the number of rounds needed for cops to win. The localization capture time conjecture claims that there exists a constant $C$ such that the localization number of every connected graph on $n$ vertices is at most $Cn$. While it is known that the conjecture holds for trees, in this paper we significantly improve the known upper bound for the localization capture time of trees. We also prove the conjecture for a subclass of outerplanar graphs and present a generalization of the localization game that appears useful for making further progress towards the conjecture.