Burning a binary tree and its generalization
share
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 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) ≤⌈√(n)⌉. 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) ≤⌈√(n)⌉ where T is the spanning tree of G. It was proved in 2018 that b(T) ≤⌈√(n + n_2 + 1/4) +1/2 ⌉ for a tree T where n_2 is the number of degree 2 vertices in T. In this article, we give an algorithm to burn a tree and we improve the existing bound using this algorithm. We prove that b(T)≤⌈√(n + n_2 + 8)⌉ -1 which is an improved bound. Also, under certain restriction of degree 2 vertices, we have improved upon the result of Bonato et al.(in 2021). We also provide an algorithm to burn a binary tree and prove the burning number conjecture for the same.
READ FULL TEXT