×

Burning spiders. (English) Zbl 1500.05043

Panda, B. S. (ed.) et al., Algorithms and discrete applied mathematics. 4th international conference, CALDAM 2018, Guwahati, India, February 15–17, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10743, 155-163 (2018).
Summary: Graph burning is a graph process modeling the spread of social contagion. Initially all the vertices of a graph \(G\) are unburned. At each step an unburned vertex is put on fire and the fire from burned vertices of the previous step spreads to their adjacent unburned vertices. This process continues till all vertices are burned. The burning number \(b(G)\) of the graph is the minimum number of steps required to burn all the vertices in the graph. The burning number conjecture by A. Bonato et al. [Internet Math. 12, No. 1–2, 85–100 (2016; Zbl 1461.05193)] states that for a connected graph \(G\) of order \(n\), its burning number \(b(G)\leq\lceil\sqrt{n}\rceil\). It is easy to observe that in order to burn a graph it is enough to burn its spanning tree. Hence it suffices to prove that for any tree \(T\) of order \(n\), its burning number \(b(T)\leq\lceil\sqrt{n}\rceil\). A spider \(S\) is a tree with one vertex of degree at least 3 and all other vertices with degree at most 2. Here we prove that for any spider \(S\) of order \(n\), its burning number \(b(S)\leq\lceil\sqrt{n}\rceil\).
For the entire collection see [Zbl 1382.68013].

MSC:

05C57 Games on graphs (graph-theoretic aspects)
05C85 Graph algorithms (graph-theoretic aspects)
91A43 Games involving graphs
91D30 Social networks; opinion dynamics

Citations:

Zbl 1461.05193
PDFBibTeX XMLCite
Full Text: DOI