2020/09/22 by Bonato, Anthony · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2009.10642
Graph burning is a deterministic, discrete-time process that models how influence or contagion spreads in a graph. Associated to each graph is its burning number, which is a parameter that quantifies how quickly the influence spreads. We survey results on graph burning, focusing on bounds, conjectures, and algorithms related to the burning number. We will discuss state-of-the-art results on the burning number conjecture, burning numbers of graph classes, and algorithmic complexity. We include a list of conjectures, variants, and open problems on graph burning.