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 ,

(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

(2)

(Land and Lu 2016, Bonato 2020).

For any graph  with graph radius  and graph diameter ,

(3)

(Bonato 2020).

Values for some parametrized families of graphs are summarized below, where  denotes the ceiling function.

family
cocktail party graph	2
crown graph	3
cycle graph
empty graph
gear graph	3
helm graph	3
ladder rung graph
odd graph
path graph
rook graph	3
star graph	{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

(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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

المجمع العلمي يواصل إقامة مسابقة الثقلين القرآنية لطلبة مدارس كربلاء

عضو مجلس إدارة العتبة العباسية المقدسة يطلع على آليات تطوير البرامج التعليمية في مجموعة العميد

مجموعة مناحل الكفيل تختتم مشاركتها في معرض السليمانية الدولي للزراعة والصناعات الغذائية

لتوثيق التراث العلمي.. وفد قسم شؤون المعارف يلتقي عددًا من أعلام مدينة النجف

المزيد

الآخبار الصحية

ثورة طبية.. الذكاء الاصطناعي يكشف سرطان الكلى في وقت قياسي

لتعزيز الطاقة والتغلب على التعب.. عليك بـ7 طرق بسيطة

لتحسين الهضم والتحكم في الشهية.. ما أفضل وقت لتناول التمر؟

خبراء يكشفون تأثير الاستحمام في الظلام على جودة النوم !

المزيد

الآخبار التكنلوجية

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

نظائر الهيليوم مقياس لاكتشاف رواسب الذهب.. كيف ذلك؟

الصين تطلق أول ناقلة نفط خام ذكية في العالم تعمل بالميثانول

الزمن على المريخ أسرع من الأرض.. دراسة علمية تكشف الفوارق

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength