The Burning Number Conjecture Holds Asymptotically
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911235268673536 |
|---|---|
| author | Norin, Sergey Turcotte, Jérémie |
| author_facet | Norin, Sergey Turcotte, Jérémie |
| contents | The burning number $b(G)$ of a graph $G$ is the smallest number of turns required to burn all vertices of a graph if at every turn a new fire is started and existing fires spread to all adjacent vertices. The Burning Number Conjecture of Bonato et al. (2016) postulates that $b(G)\leq \left\lceil\sqrt{n}\right\rceil$ for all graphs $G$ on $n$ vertices. We prove that this conjecture holds asymptotically, that is $b(G)\leq (1+o(1))\sqrt n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_04035 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The Burning Number Conjecture Holds Asymptotically Norin, Sergey Turcotte, Jérémie Combinatorics Discrete Mathematics 05C57 (Primary) 05C82, 05C05 (Secondary) The burning number $b(G)$ of a graph $G$ is the smallest number of turns required to burn all vertices of a graph if at every turn a new fire is started and existing fires spread to all adjacent vertices. The Burning Number Conjecture of Bonato et al. (2016) postulates that $b(G)\leq \left\lceil\sqrt{n}\right\rceil$ for all graphs $G$ on $n$ vertices. We prove that this conjecture holds asymptotically, that is $b(G)\leq (1+o(1))\sqrt n$. |
| title | The Burning Number Conjecture Holds Asymptotically |
| topic | Combinatorics Discrete Mathematics 05C57 (Primary) 05C82, 05C05 (Secondary) |
| url | https://arxiv.org/abs/2207.04035 |