The localization game on oriented graphs

被引：0

作者：

Bonato, Anthony ^{[1
]}

Cushman, Ryan ^{[2
]}

Marbach, Trent G. ^{[1
]}

Pittman, Brittany ^{[1
]}

机构：

[1] Toronto Metropolitan Univ, Toronto, ON, Canada

[2] Univ Wisconsin Eau Claire, Eau Claire, WI USA

来源：

DISCRETE APPLIED MATHEMATICS | 2023年 / 338卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

Oriented graphs; Localization number; Strong components; Hypergraphs; Tournaments; Random tournaments; Quasi -random tournaments; Paley tournaments; METRIC DIMENSION; ROBBER; NUMBER;

D O I：

10.1016/j.dam.2023.06.003

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 oriented graphs. We present several bounds on the localization number of an oriented graph, including a tight bound via strong components, a bound using a linear programming problem on hypergraphs, and bounds in terms of DAG-width. A family of oriented graphs of order n is given with localization number (1 - o(1))n/2. We investigate the localization number of random and quasi-random tournaments, including Paley tournaments.& COPY; 2023 Elsevier B.V. All rights reserved.

引用

页码：145 / 157

页数：13

共 38 条

[1]

Bang-Jensen J, 2009, SPRINGER MONOGR MATH, P1, DOI 10.1007/978-1-84800-998-1_1

[2] The localization capture time of a graph [J].

Behague, Natalie C. ;

Bonato, Anthony ;

Huggan, Melissa A. ;

Marbach, Trent G. ;

Pittman, Brittany .

THEORETICAL COMPUTER SCIENCE, 2022, 911 :80-91

[3] Metric Dimension: from Graphs to Oriented Graphs [J].

Bensmail, Julien ;

Mc Inerney, Fionn ;

Nisse, Nicolas .

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2019, 346 :111-123

[4]

Bertsimas D., 1997, Introduction to Linear Optimization

[5] The DAG-width of directed graphs [J].

Berwanger, Dietmar ;

Dawar, Anuj ;

Hunter, Paul ;

Kreutzer, Stephan ;

Obdrzalek, Jan .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2012, 102 (04) :900-923

[6]

Biedl T.C., 2023, PREPRINT

[7]

Bollobás B, 2013, ELECTRON J COMB, V20

[8]

Bonato A., 2017, Graph searching games and probabilistic methods

[9]

Bonato A., 2011, The Game of Cops and Robbers on Graphs

[10]

Bonato A, 2022, An Invitation to Pursuit-Evasion Games and Graph Theory

← 1 2 3 4 →