Burning game
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_ | 1866916397835091968 |
|---|---|
| author | Chiarelli, Nina Iršič, Vesna Jakovac, Marko Kinnersley, William B. Mikalački, Mirjana |
| author_facet | Chiarelli, Nina Iršič, Vesna Jakovac, Marko Kinnersley, William B. Mikalački, Mirjana |
| contents | Motivated by the burning and cooling processes, the burning game is introduced. The game is played on a graph $G$ by the two players (Burner and Staller) that take turns selecting vertices of $G$ to burn; as in the burning process, burning vertices spread fire to unburned neighbors. Burner aims to burn all vertices of $G$ as quickly as possible, while Staller wants the process to last as long as possible. If both players play optimally, then the number of time steps needed to burn the whole graph $G$ is the game burning number $b_g(G)$ if Burner makes the first move, and the Staller-start game burning number $b_g'(G)$ if Staller starts. In this paper, basic bounds on $b_g(G)$ are given and Continuation Principle is established. Graphs with small game burning numbers are characterized and Nordhaus-Gaddum type results are obtained. An analogue of the burning number conjecture for the burning game is considered and graph products are studied. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_11328 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Burning game Chiarelli, Nina Iršič, Vesna Jakovac, Marko Kinnersley, William B. Mikalački, Mirjana Combinatorics 05C57 Motivated by the burning and cooling processes, the burning game is introduced. The game is played on a graph $G$ by the two players (Burner and Staller) that take turns selecting vertices of $G$ to burn; as in the burning process, burning vertices spread fire to unburned neighbors. Burner aims to burn all vertices of $G$ as quickly as possible, while Staller wants the process to last as long as possible. If both players play optimally, then the number of time steps needed to burn the whole graph $G$ is the game burning number $b_g(G)$ if Burner makes the first move, and the Staller-start game burning number $b_g'(G)$ if Staller starts. In this paper, basic bounds on $b_g(G)$ are given and Continuation Principle is established. Graphs with small game burning numbers are characterized and Nordhaus-Gaddum type results are obtained. An analogue of the burning number conjecture for the burning game is considered and graph products are studied. |
| title | Burning game |
| topic | Combinatorics 05C57 |
| url | https://arxiv.org/abs/2409.11328 |