The localization game is a pursuit-evasion game analogous to Cops and Robbers, where the robber is invisible and the cops send distance probes in an attempt to identify the location of the robber. We present a novel graph parameter called the capture time, which measures how long the localization game lasts assuming optimal play. We conjecture that the capture time is linear in the order of the graph, and show that the conjecture holds for graph families such as trees and interval graphs. We study bounds on the capture time for trees and its monotone property on induced subgraphs of trees and more general graphs. We give upper bounds for the capture time on the incidence graphs of projective planes. We finish with new bounds on the localization number and capture time using treewidth.
翻译:本地化游戏是一个类似于Cops和Robbers的追逐避险游戏, 抢匪是隐形的, 警方发送了远程探测器, 试图识别强盗的位置 。 我们展示了一个叫做抓捕时间的新型图形参数, 用来测量本地化游戏持续的时间, 以最佳游戏为最佳游戏。 我们推测抓捕时间按图表的顺序是线性的, 并显示图式家庭( 如树和间距图) 的猜想。 我们研究树木的捕捉时间和树的单体属性, 并研究树木的诱导子图和更普通的图形。 我们给投影式飞机的事件图表的捕捉时间以上方的上限 。 我们用本地化数字完成新的界限, 并用树丝来捕捉时间 。