On The Burning Numbers Of K-cactus Graph

Burning number is an important field,and it is a discrete time graph process that can be interpreted as a model for the spread of influence in social networks,mainly involving the spread of viruses,messages,etc.In a graph G,the burning number of it is the minimum number of steps in a graph burning process.It is shown that the graph burning problem is NP-complete even for the simple graph classes,like as trees and path-forests.In this thesis,we will mainly study the bound on the burning number of k-cactus graph,and according to the existing conclusion:the burning numbers of path-forests with at most three components,we will use these two results as the significant tools to prove this thesis,and then give some necessary and sufficient conditions for the k*-cactus graph to have burning numbers.The content distribution is as follows:Chapter 1 describes the background and significance of the graph burning,gives some theorems and lemmas about burning number,and summarizes the main contents of this thesis.Chapter 2 shows that the bound on the burning number of k-cactus graph.Chapter 3,4 According to the bound on the burning number of k-cactus graph,and the burning numbers of path-forests with at most three components,using these two results as the significant tools to prove this thesis,we will respectively give some necessary and sufficient conditions for the 5*-cactus graph and 6*-cactus graph to have burning numbers q-1,q,or q+1.Chapter 5 gives a brief summary of the research contents in this thesis.