2023/08/05 by Sandip Das, Sk Samim Islam, Das, Sandip +5 · 2 citations
Computer Science · Physics and Astronomy · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complex Network Analysis Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2308.02825
openalex publication_date 2023/08/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Graph burning is a graph process that models the spread of social contagion. Initially, all the vertices of a graph G are unburnt. At each step, an unburnt vertex is put on fire and the fire from burnt vertices of the previous step spreads to their adjacent unburnt vertices. This process continues till all the vertices are burnt. The burning number b(G) of the graph G is the minimum number of steps required to burn all the vertices in the graph. The burning number conjecture by Bonato et al. states that for a connected graph G of order n, its burning number b(G) ≤ \lceil √(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) ≤ \lceil √(n) \rceil where T is the spanning tree of G. It was proved in 2018 that b(T) ≤ \lceil √(n + n2 + 1/4) +1/2 \rceil for a tree T where n2 is the number of degree 2 vertices in T. In this paper, we provide an algorithm to burn a tree and we improve the existing bound using this algorithm. We prove that b(T)≤ \lceil √(n + n2 + 8)\rceil -1 which is an improved bound for n≥ 50. We also provide an algorithm to burn some subclasses of the binary tree and prove the burning number conjecture for the same.