Burning games on strong path products
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_ | 1866912625143578624 |
|---|---|
| author | Ambrose, Sally Angelone, Evan Chen, Jacob Ma, Daniel Miguel, Arturo Ortiz San Watanabe, Wraven Whitcomb, Stephen Wu, Shanghao |
| author_facet | Ambrose, Sally Angelone, Evan Chen, Jacob Ma, Daniel Miguel, Arturo Ortiz San Watanabe, Wraven Whitcomb, Stephen Wu, Shanghao |
| contents | Burning and cooling are diffusion processes on graphs in which burned (or cooled) vertices spread to their neighbors with a new source picked at discrete time steps. In burning, the one tries to burn the graph as fast as possible, while in cooling one wants to delay cooling as long as possible.
We consider $d$-fold strong products of paths, which generalize king graphs. The propagation of these graphs is radial, and models local spread of contagion in an arbitrary number of dimensions. We reduce the problem to a geometric tiling problem to obtain a bound for the burning number of a strong product of paths by a novel use of an Euler-Maclaurin formula, which is sharp under certain number theoretic conditions.
Additionally, we consider liminal burning, which is a two-player perfect knowledge game played on graphs related to the effectiveness of controlled spread of contagion throughout a network. We introduce and study the number $k^*$, the smallest $k$ such that $b_{k}(G) = b(G)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_20572 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Burning games on strong path products Ambrose, Sally Angelone, Evan Chen, Jacob Ma, Daniel Miguel, Arturo Ortiz San Watanabe, Wraven Whitcomb, Stephen Wu, Shanghao Combinatorics 2020 MSC: 05C57 (Primary), 91A43 (Secondary) Burning and cooling are diffusion processes on graphs in which burned (or cooled) vertices spread to their neighbors with a new source picked at discrete time steps. In burning, the one tries to burn the graph as fast as possible, while in cooling one wants to delay cooling as long as possible. We consider $d$-fold strong products of paths, which generalize king graphs. The propagation of these graphs is radial, and models local spread of contagion in an arbitrary number of dimensions. We reduce the problem to a geometric tiling problem to obtain a bound for the burning number of a strong product of paths by a novel use of an Euler-Maclaurin formula, which is sharp under certain number theoretic conditions. Additionally, we consider liminal burning, which is a two-player perfect knowledge game played on graphs related to the effectiveness of controlled spread of contagion throughout a network. We introduce and study the number $k^*$, the smallest $k$ such that $b_{k}(G) = b(G)$. |
| title | Burning games on strong path products |
| topic | Combinatorics 2020 MSC: 05C57 (Primary), 91A43 (Secondary) |
| url | https://arxiv.org/abs/2509.20572 |