The Localization game on locally finite trees

Anthony Bonato; Florian Lehner; Trent Marbach; Jd Nir

doi:10.5817/CZ.MUNI.EUROCOMB23-021

The Localization game on locally finite trees

EUROCOMB’23

Anthony Bonato Florian Lehner Trent Marbach Jd Nir

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-021

PDF

Abstract

We study the Localization game on locally finite graphs and trees, where each vertex has finite degree. As in finite graphs, we prove that any locally finite graph contains a subdivision where one cop can capture the robber. In contrast to the finite case, for $n$ a positive integer, we construct a locally finite tree with localization number $n$ for any choice of $n$. Such trees contain uncountably many ends, and we show this is necessary by proving that graphs with countably many ends have localization number at most 2. We finish with questions on characterizing the localization number of locally finite trees.

Pages:
149–155

References

N.C. Behague, A. Bonato, M.A. Huggan, T.G. Marbach, and B. Pittman, The localization capture time of a graph, Theoretical Computer Science, 911:80-91, 2022.
https://doi.org/10.1016/j.tcs.2022.02.007

A. Bonato, An Invitation to Pursuit-Evasion Games and Graph Theory, American Mathematical Society, Providence, Rhode Island, 2022.
https://doi.org/10.1090/stml/097

A. Bonato, G. Hahn, and C. Tardif, Large classes of infinite k-cop-win graphs, Journal of Graph Theory, 65:334--342, 2010.
https://doi.org/10.1002/jgt.20484

A.~Bonato, M.A. Huggan, and T. Marbach, The localization number of designs, Journal of Combinatorial Designs, 29:175--192, 2021.
https://doi.org/10.1002/jcd.21762

A. Bonato and W. Kinnersley, Bounds on the localization number, Journal of Graph Theory, 94:1--18, 2020.
https://doi.org/10.1002/jgt.22546

A. Bonato and R.J. Nowakowski, The Game of Cops and Robbers on Graphs, American Mathematical Society, Providence, Rhode Island, 2011.
https://doi.org/10.1090/stml/061

B. Bosek, P. Gordinowicz, J. Grytczuk, N. Nisse, J. Sok'ol, and M. 'Sleszy'nska-Nowak, Localization game on geometric and planar graphs, Discrete Applied Mathematics, 251:30--39, 2018.
https://doi.org/10.1016/j.dam.2018.04.017

B. Bosek, P. Gordinowicz, J. Grytczuk, N. Nisse, J. Sok'ol, and M. 'Sleszy'nska-Nowak, Centroidal localization game, Electronic Journal of Combinatorics, 25(4):P4.62, 2018.
https://doi.org/10.37236/7488

A. Brandt, J. Diemunsch, C. Erbes, J. LeGrand, and C. Moffatt, A robber locating strategy for trees, Discrete Applied Mathematics, 232:99--106, 2017.
https://doi.org/10.1016/j.dam.2017.07.019

J. Carraher, I. Choi, M. Delcourt, L.H. Erickson, and D.B. West, Locating a robber on a graph via distance queries, Theoretical Computer Science, 463:54--61, 2012.
https://doi.org/10.1016/j.tcs.2012.06.035

R. Diestel, Graph Theory, American Springer Berlin, Heidelberg, Germany, 2017.
https://doi.org/10.1007/978-3-662-53622-3

G. Hahn, F. Laviolette, N. Sauer, and R.E. Woodrow, On cop-win graphs, Discrete Mathematics, 258:27--41, 2002.
https://doi.org/10.1016/S0012-365X(02)00260-1

J. Haslegrave, R.A. Johnson, and S. Koch, Locating a robber with multiple probes, Discrete Mathematics, 341: 184--193, 2018.
https://doi.org/10.1016/j.disc.2017.08.028

M.R. Ivan, I. Leader, and M. Walters, Constructible graphs and pursuit, Theoretical Computer Science, 930: 196--208, 2022.
https://doi.org/10.1016/j.tcs.2022.07.023

F. Lehner, Pursuit evasion on infinite graphs, Theoretical Computer Science, 655(A):30--40, 2016.
https://doi.org/10.1016/j.tcs.2016.04.024

S. Seager, Locating a robber on a graph, Discrete Mathematics, 312:3265--3269, 2012.
https://doi.org/10.1016/j.disc.2012.07.029

S. Seager, Locating a backtracking robber on a tree, Theoretical Computer Science, 539:28--37, 2014.
https://doi.org/10.1016/j.tcs.2014.04.019

Metrics