论文标题
在定向图上的本地化游戏
The Localization Game on Directed Graphs
论文作者
论文摘要
在图形上播放的本地化游戏中，一组警察使用距离探针来识别无形强盗的位置。我们将游戏及其主要参数（本地化编号）的扩展为有向图。我们在有向图的定位数上介绍了几个界限，包括通过强组件的紧密绑定，使用超图上的线性编程问题的绑定，以及在路径宽度和DAG宽度方面的边界。订单$ n $的digraphs家族与本地化编号$（1-o（1））N/2 $一起提供。我们调查了随机和准随机锦标赛的本地化数量，并将结果应用于包括Paley锦标赛在内的双重常规比赛。
In the Localization game played on graphs, a set of cops uses distance probes to identify the location of an invisible robber. We present an extension of the game and its main parameter, the localization number, to directed graphs. We present several bounds on the localization number of a directed graphs, including a tight bound via strong components, a bound using a linear programming problem on hypergraphs, and bounds in terms of pathwidth and DAG-width. A family of digraphs of order $n$ is given with localization number $(1-o(1))n/2$. We investigate the localization number of random and quasi-random tournaments, and apply our results to doubly regular tournaments, which include Paley tournaments.
