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.

اخر الاخبار

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

جولة تفقدية لمتابعة خطة تنظيم مداخل المعزّين المشاركين في عزاء ركضة طويريج

لتعزيز التعاون الأكاديمي والبحثي.. جامعة الكفيل توقع اتفاقيتي توأمة مع جامعتين عراقيتين

المجمَع العلميّ يواصل إقامة مجلسه العزائي بذكرى شهادة الإمام الحسين (عليه السلام) في النجف الأشرف

قسم حفظ النظام يواصل تنفيذ خطته لتنظيم سير المواكب والزائرين في شهر المحرم

المزيد

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

لهذا السبب.. إغلاق 25 مركزًا لعلاج الإدمان في مصر ؟

خلافا للاعتقاد الشائع.. علماء يكشفون أسرار بذور البطيخ ؟!

هذا ما يحدث لجسمك عند تناولك الطماطم بانتظام !

تعرف على أطعمة تسرّع "تعافي الجسم" من حروق الشمس

المزيد

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

الثلوج تغطي الصحراء الأكثر جفافا في العالم!

بتلسكوب "ألما".. التقاط صورا غير مسبوقة لبدايات الكون !

هل هاتفك مراقب؟.. 5 علامات خطيرة تكشف التجسس عليك

دبي تطلق أول رحلة تجريبية للتاكسي الجوي

المزيد

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

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