Das, Sandip; Dev, Subhadeep Ranjan; Sadhukhan, Arpan; Sahoo, Uma kant; Sen, Sagnik 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]. Cited in 10 Documents MSC: 05C57 Games on graphs (graph-theoretic aspects) 05C85 Graph algorithms (graph-theoretic aspects) 91A43 Games involving graphs 91D30 Social networks; opinion dynamics Keywords:graph burning; burning number conjecture Citations:Zbl 1461.05193 PDFBibTeX XMLCite \textit{S. Das} et al., Lect. Notes Comput. Sci. 10743, 155--163 (2018; Zbl 1500.05043) Full Text: DOI