Localization game capture time of trees and outerplanar graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915782935445504 |
|---|---|
| author | Chenoweth, Vesna Iršič Skrt, Matija |
| author_facet | Chenoweth, Vesna Iršič Skrt, Matija |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_10443 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Localization game capture time of trees and outerplanar graphs Chenoweth, Vesna Iršič Skrt, Matija Combinatorics Discrete Mathematics 05C57, 05C12, 05C05 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. |
| title | Localization game capture time of trees and outerplanar graphs |
| topic | Combinatorics Discrete Mathematics 05C57, 05C12, 05C05 |
| url | https://arxiv.org/abs/2508.10443 |