Burning Number
المؤلف:
Bessy, S.; Bonato, A.; Jansen, J.; Rautenbach, D.; and Roshanbin, E
المصدر:
"Bounds on the Burning Number." 2 Nov 2016. https://arxiv.org/abs/1511.06023.
الجزء والصفحة:
...
15-5-2022
1983
Burning Number
Bonato et al. (2014, 2015) defined the burning number of a simple graph as follows. Consider a process called burning involving are discrete time steps. Each node is either burned or unburned; if a node is burned, then it remains in that state until the end of the process. In every round, choose one additional unburned node to burn (if such a node is available). Once a node is burned in round 
, in round 
, each of its unburned neighbors becomes burned. The process ends when all nodes are burned. The burning number of a graph 
, written by 
, is then defined as the minimum number of rounds needed for the process to end.
Bonato et al. (2015) showed that for a traceable graph 
with vertex count 
,
![b(g)<=[sqrt(n)],](https://mathworld.wolfram.com/images/equations/BurningNumber/NumberedEquation1.svg) |
(1)
|
and conjecture that this inequality holds for any connected graph. Bonato (2020) calls this statement the "burning number conjecture," and terms any graph that satisfies the inequality "well-burnable." The best known upper bound is given by
![b(G)<=[(-3+sqrt(24n+33))/4]](https://mathworld.wolfram.com/images/equations/BurningNumber/NumberedEquation2.svg) |
(2)
|
(Land and Lu 2016, Bonato 2020).
For any graph 
with graph radius 
and graph diameter 
,
![[sqrt(d+1)]<=b(G)<=r+1](https://mathworld.wolfram.com/images/equations/BurningNumber/NumberedEquation3.svg) |
(3)
|
(Bonato 2020).
Values for some parametrized families of graphs are summarized below, where ![[n]](https://mathworld.wolfram.com/images/equations/BurningNumber/Inline10.svg)
denotes the ceiling function.
| family |
 |
cocktail party graph  |
2 |
crown graph  |
3 |
cycle graph  |
![[sqrt(n)]](https://mathworld.wolfram.com/images/equations/BurningNumber/Inline15.svg) |
empty graph  |
 |
| gear graph |
3 |
| helm graph |
3 |
ladder rung graph  |
 |
odd graph  |
 |
path graph  |
![[sqrt(n)]](https://mathworld.wolfram.com/images/equations/BurningNumber/Inline23.svg) |
rook graph  |
3 |
star graph  |
![<span style=]() {1 for n=1; 2 otherwise" src="https://mathworld.wolfram.com/images/equations/BurningNumber/Inline26.svg" style="height:68px; width:130px" /> |
| sun graph |
3 |
transposition graph  |
 |
wheel graph  |
2 |
In addition, the hypercube graph 
satisfies 
up to at least 
. The Möbius ladder agrees with AA155934 up to at least 
.
Bonato et al. (2015) show that
![[sqrt(d+1)]<=b(G)<=r+1,](https://mathworld.wolfram.com/images/equations/BurningNumber/NumberedEquation4.svg) |
(4)
|
where 
is the graph diameter and 
is the graph radius of a graph 
as well as that graph complement of 
, then
 |
(5)
|
if 
is the graph complement of 
.
REFERENCES
Bessy, S.; Bonato, A.; Jansen, J.; Rautenbach, D.; and Roshanbin, E. "Bounds on the Burning Number." 2 Nov 2016. https://arxiv.org/abs/1511.06023.
Bonato, S. "A Survey of Graph Burning." 22 Sep 2020. https://arxiv.org/abs/2009.10642v1.
Bonato, A.; Janssen, J.; and Roshanbin, E. "Burning a Graph as a Model of Social Contagion." In Algorithms and Models for the Web Graph: 11th International Workshop, WAW 2014, Beijing, China, December 17-18, 2014, Proceedings (
Ed. A. Bonato A., F. Graham F., and P. Prałat). Springer, pp. 13-22, 2014.
Bonato, A.; Janssen, J.; and Roshanbin, E. "How to Burn a Graph." To appear in Internet Mathematics. 23 Jul 2015. https://arxiv.org/abs/1507.06524.
Land, M. and Lu, L. "An Upper Bound on Burning Number of Graphs." In Proceedings of WAW'16. 2016.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
