The Burning Number Of Some Classes Of Trees

Graph burning is a deterministic discrete time graph process and burning also can be viewed as a simplified model for the spread of social contagion in a social network such as Facebook or Twitter.For example,the fireman problem,the graph cleaning problem,the graph guidance precoding and other problems are all related to it.The burning number of a graph is the minimum number of steps in a graph burning process.It was introduced by Bonato in 2014.Bonato conjectured that b(G)??(?)for any connected graph G of order n.Bonato and Lidbetter considered the bounds on the burning numbers of spiders(which are trees with exactly one vertex of degree strictly greater than two)and path-forests.Sim studied the burning number of generalized Petersen graphs.Very recently,Liu considered the burning number of theta graphs.It is shown that the graph burning problem is NP-complete even for trees with maximum degree three and path-forests(that is,disjoint unions of paths).Since the burning number is a relatively new parameter,it is also interesting to determine the burning number of special classes of graphs.In this paper,we mainly study the burning number of some special classes of trees,including the following aspects:(1)According to the conjecture of Bonato,this paper proves that the caterpillars satisfy the conjecture by the method of minimum counterexample,that is,we give the upper bound of caterpillars;(2)In this paper,the upper and lower bounds of the burning numbers of caterpil-lars with at most two stems and caterpillars all of whose spine vertices are stems are determined respectively by the lemma and related research methods proposed by Li-u Huiqing and others.Therefore,the accurate values of the burning number of these special caterpillars are obtained;(3)For spiders with three arms of order n,this paper first finds the lower bound of the burning number of spiders,and then locks the burning number of spiders into two determined values[(?)and?(?).Next,In this paper,we give the sufficient con-ditions that the burning number of spiders is equal to ?(?)and?(?)respectively.Therefore,we determine the burning numbers of all spiders with three arms.