Improved Pyrotechnics: Closer to the Burning Number Conjecture
The Electronic Journal of Combinatorics · 06.10.2023 · 30 (4)
DOI: 10.37236/11113 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 06.10.2023. Verfasst von Paul Bastide und 6 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref).
Abstract (Originalsprache)
The Burning Number Conjecture claims that for every connected graph $G$ of order $n,$ its burning number satisfies $b(G) \le \lceil \sqrt{n}\, \rceil.$ While the conjecture remains open, we prove that it is asymptotically true when the order of the graph is much larger than its growth, which is the maximal distance of a vertex to a well-chosen path in the graph. We prove that the conjecture for graphs of bounded growth reduces to a finite number of cases. We provide the best-known bound on the burning number of a connected graph $G$ of order $n,$ given by $b(G) \le \sqrt{4n/3} + 1,$ improving on the previously known $\sqrt{3n/2}+O(1)$ bound. Using the improved upper bound, we show that the conjecture almost holds for all graphs with minimum degree at least $3$ and holds for all large enough graphs with minimum degree at least $4$. The previous best-known result was for graphs with minimum degree $23$.
Zitieren
APA
Bastide, P., Bonamy, M., Bonato, A., Charbit, P., Kamali, S., Pierron, T., & Rabie, M. (2023). Improved Pyrotechnics: Closer to the Burning Number Conjecture. The Electronic Journal of Combinatorics, 30(4). https://doi.org/10.37236/11113
Vancouver
Bastide P, Bonamy M, Bonato A, Charbit P, Kamali S, Pierron T, et al. Improved Pyrotechnics: Closer to the Burning Number Conjecture. The Electronic Journal of Combinatorics. 2023;30(4). doi:10.37236/11113
BibTeX
@article{Bastide2023,
author = {Bastide, Paul and Bonamy, Marthe and Bonato, Anthony and Charbit, Pierre and Kamali, Shahin and Pierron, Théo and Rabie, Mikaël},
title = {Improved Pyrotechnics: Closer to the Burning Number Conjecture},
journal = {The Electronic Journal of Combinatorics},
year = {2023},
volume = {30},
number = {4},
doi = {10.37236/11113}
}
EUVIMED