2021/03/14 by Ruiting Zhang, Yingying Yu, Zhang, Ruiting +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Interconnection Networks and Systems #math.CO
paper · pdf · doi:10.48550/arxiv.2103.07840
arxiv created 2021/03/14 · arxiv updated 2021/03/16
Given a graph G, the burning number of G is the smallest integer k for which there are vertices x1, x2,…,xk such that (x1,x2,…,xk) is a burning sequence of G. It has been shown that the graph burning problem is NP-complete, even for trees with maximum degree three, or linear forests. A t-unicyclic graph is a unicycle graph with exactly one vertex of degree greater than 2. In this paper, we first present the bounds for the burning number of t-unicyclic graphs, and then use the burning numbers of linear forests with at most three components to determine the burning number of all t-unicyclic graphs for t≤ 2.