The capture time in the game of cops and many robbers
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916947368607744 |
|---|---|
| author | Gyergyek, Miha Chenoweth, Vesna Iršič |
| author_facet | Gyergyek, Miha Chenoweth, Vesna Iršič |
| contents | The game of cops and robber is a pursuit-evasion game played on graphs that has been extensively studied. Traditionally the game is played with one or more cops and only one robber, but in this paper we consider the game played with multiple robbers, with rules allowing for consecutive capture of the robbers. While the cop number remains the same, the capture time can differ drastically compared to the game played with one robber. In this paper we present general upper bounds for the capture time of cop-win graphs in the game with multiple robbers and show that they are the best possible for some families of graphs. Moreover, we explore how the capture time behaves with an increasing number of robbers and prove a surprising relation between this behavior and the 0-visibility cop number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_10022 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The capture time in the game of cops and many robbers Gyergyek, Miha Chenoweth, Vesna Iršič Combinatorics 05C57, 05C05, 05C75 The game of cops and robber is a pursuit-evasion game played on graphs that has been extensively studied. Traditionally the game is played with one or more cops and only one robber, but in this paper we consider the game played with multiple robbers, with rules allowing for consecutive capture of the robbers. While the cop number remains the same, the capture time can differ drastically compared to the game played with one robber. In this paper we present general upper bounds for the capture time of cop-win graphs in the game with multiple robbers and show that they are the best possible for some families of graphs. Moreover, we explore how the capture time behaves with an increasing number of robbers and prove a surprising relation between this behavior and the 0-visibility cop number. |
| title | The capture time in the game of cops and many robbers |
| topic | Combinatorics 05C57, 05C05, 05C75 |
| url | https://arxiv.org/abs/2509.10022 |