A cop-robber game on metric graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909972505296896 |
|---|---|
| author | Berend, Daniel Boshernitzan, Michael D. |
| author_facet | Berend, Daniel Boshernitzan, Michael D. |
| contents | We study a variant of the classical cop-robber game played on compact metric graphs, where each edge is assigned a positive length and identified with a real interval of corresponding length. In this setting, both the cop and the robber move continuously along the edges, subject to upper bounds on their speeds. The cop has no knowledge of the robber's location and must choose a continuous path through the graph that is guaranteed to intersect the robber's trajectory at some point in time. We show that for every compact metric graph, there exists a constant s > 0 such that if the cop's speed exceeds s times the robber's speed, then the cop can guarantee capture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_18468 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A cop-robber game on metric graphs Berend, Daniel Boshernitzan, Michael D. Combinatorics Primary 05C57, Secondary 05C12, 91A44, 49N75 We study a variant of the classical cop-robber game played on compact metric graphs, where each edge is assigned a positive length and identified with a real interval of corresponding length. In this setting, both the cop and the robber move continuously along the edges, subject to upper bounds on their speeds. The cop has no knowledge of the robber's location and must choose a continuous path through the graph that is guaranteed to intersect the robber's trajectory at some point in time. We show that for every compact metric graph, there exists a constant s > 0 such that if the cop's speed exceeds s times the robber's speed, then the cop can guarantee capture. |
| title | A cop-robber game on metric graphs |
| topic | Combinatorics Primary 05C57, Secondary 05C12, 91A44, 49N75 |
| url | https://arxiv.org/abs/2512.18468 |