Locally finite graphs and their localization numbers
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909159441563648 |
|---|---|
| author | Bonato, Anthony Lehner, Florian Marbach, Trent G. Nir, JD |
| author_facet | Bonato, Anthony Lehner, Florian Marbach, Trent G. Nir, JD |
| contents | We study the Localization game on locally finite graphs trees, where each of the countably many vertices have finite degree. In contrast to the finite case, we construct a locally finite tree with localization number $n$ for any choice of positive integer $n$. Our examples have uncountably many ends, and we show that this is necessary by proving that locally finite trees with finitely or countably many ends have localization number at most 2. Finally, as is the case for finite graphs, we prove that any locally finite graph contains a subdivision where one cop can capture the robber. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_02409 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Locally finite graphs and their localization numbers Bonato, Anthony Lehner, Florian Marbach, Trent G. Nir, JD Combinatorics We study the Localization game on locally finite graphs trees, where each of the countably many vertices have finite degree. In contrast to the finite case, we construct a locally finite tree with localization number $n$ for any choice of positive integer $n$. Our examples have uncountably many ends, and we show that this is necessary by proving that locally finite trees with finitely or countably many ends have localization number at most 2. Finally, as is the case for finite graphs, we prove that any locally finite graph contains a subdivision where one cop can capture the robber. |
| title | Locally finite graphs and their localization numbers |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2404.02409 |