2023/12/21 by Yukihiro Murakami, Murakami, Yukihiro · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2312.13972
openalex publication_date 2023/12/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Graph burning is a discrete time process which can be used to model the spread of social contagion. One is initially given a graph of unburned vertices. At each round (time step), one vertex is burned; unburned vertices with at least one burned neighbour from the previous round also becomes burned. The burning number of a graph is the fewest number of rounds required to burn the graph. It has been conjectured that for a graph on n vertices, the burning number is at most \lceil√(n)\rceil. We show that the graph burning conjecture is true for trees without degree-2 vertices.