A survey of graph burning

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.

• Publication year

  2020

• Venue

  Contributions Discret. Math.

• Publication date

  2020-09-22

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.11575/CDM.V16I1.71194arXiv 2009.10642
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Burning Number of Directed Graphs: Bounds and Computational Complexity

  2020cited by this paper
• Faster heuristics for graph burning

  2020cited by this paper
• Parameterized Complexity of Graph Burning

  2020cited by this paper
• APX-Hardness and Approximation for the k-Burning Number Problem

  2020cited by this paper
• Burning number of caterpillars

  2020cited by this paper
• NP-completeness Results for Graph Burning on Geometric Graphs

  2020cited by this paper
• Parameterized Algorithms for Graph Burning Problem

  2019influential reference
• On the Burning Number of p-Caterpillars

  2019influential reference
• Improved Bounds for Burning Fence Graphs

  2019cited by this paper
• Graph burning: Tight bounds on the burning numbers of path forests and spiders

  2019cited by this paper
• Burning Two Worlds: Algorithms for Burning Dense and Tree-like Graphs

  2019cited by this paper
• Burning number of theta graphs

  2019cited by this paper
• Burning number of graph products

  2018cited by this paper
• Approximation Algorithms for Graph Burning

  2018influential reference
• On the Burning Number of Generalized Petersen Graphs

  2018cited by this paper
• Burning Spiders

  2018cited by this paper
• Burning the Plane

  2018cited by this paper
• Bounds on the burning numbers of spiders and path-forests

  2017cited by this paper
• Throttling for the game of Cops and Robbers on graphs

  2017cited by this paper
• Burning Circulant Graphs.

  2017cited by this paper
• Graph Searching Games and Probabilistic Methods

  2017cited by this paper
• An Upper Bound on the Burning Number of Graphs

  2016cited by this paper
• Bounds on the burning number

  2015cited by this paper
• How to Burn a Graph

  2015influential reference
• Burning graphs - a probabilistic perspective

  2015influential reference
• Burning a graph is hard

  2015cited by this paper
• Burning a Graph as a Model of Social Contagion

  2014cited by this paper
• The Design of Approximation Algorithms

  2011cited by this paper
• The Game of Cops and Robbers on Graphs

  2011cited by this paper
• The Firefighter Problem: a survey of results, directions and questions

  2009cited by this paper
• Tree-decompositions with bags of small diameter

  2007cited by this paper
• Random graphs

  2006cited by this paper
• Maximizing the spread of influence through a social network

  2003cited by this paper
• Random graphs

  1996cited by this paper
• Introduction to Graph Theory

  1995cited by this paper
• Introduction to the theory of computation

  1989cited by this paper

• Propagation processes on (hyper)graphs: where zero forcing and burning meet

  2026cites this paper
• The burning game on graphs

  2026cites this paper
• The Independent Cascade Graph Burning for Operation Graphs

  2025cites this paper
• Graph burning: an overview of mathematical programs

  2025cites this paper
• Burning numbers via eigenpolytopes -- Hamming graphs, Johnson graphs, and halved cubes

  2025cites this paper
• From Burning Extremal Balanced Spiders Into Properties for Generalization to All Trees

  2025cites this paper
• Between burning and cooling: liminal burning on graphs

  2025cites this paper
• Complexity of Firefighting on Graphs

  2025cites this paper
• A New Dominating Set Game on Graphs

  2025cites this paper
• Can Non-Signaling Assistance Increase the Degrees of Freedom of a Wireless Network?

  2025cites this paper
• Orientable burning number of graphs

  2025cites this paper
• Upper bounds and approximation results for the k-slow burning problem

  2025cites this paper
• The Generalized Burning Number of Gear Graph and Sun Graph

  2025cites this paper
• Can Non-Signaling Assistance Increase the Degrees of Freedom of a Wireless Network?

  2025cites this paper
• Graph Burning in Community-based Networks

  2024influential citation
• How to Cool a Graph

  2024cites this paper
• A greedy heuristic for graph burning

  2024cites this paper
• Graph Burning: Bounds and Hardness

  2024cites this paper
• Extending graph burning to hypergraphs

  2024cites this paper
• Burning Numbers of Barbells

  2024cites this paper
• Burning Hamming graphs

  2024cites this paper
• The Burning Number Conjecture is True for Trees without Degree-2 Vertices

  2024influential citation
• Homology of graph burnings

  2024influential citation
• How to Burn a Latin Square

  2024cites this paper
• Revolutionizing Smart Agriculture: Burning Number Analysis and Linear Regression for Optimal Sensor Activation in 3-Ary n-Cube Networks

  2024cites this paper
• Proportion-Based Hypergraph Burning

  2024cites this paper
• Burning game

  2024cites this paper
• Solving the Graph Burning Problem for Large Graphs

  2024cites this paper
• The 2 -burning Number of a Graph

  2024cites this paper
• Hypergraph burning, matchings, and zero forcing

  2024cites this paper
• Graph Burning On Large $p$-Caterpillars

  2024cites this paper
• Approximation Algorithms and Lower Bounds for Graph Burning

  2023cites this paper
• On the approximability of the burning number

  2023cites this paper
• A centrality based genetic algorithm for the graph burning problem

  2023cites this paper
• The Graph Burning Conjecture is true for trees without degree-2 vertices

  2023influential citation
• A Note on Graph Burning of Path Forests

  2023cites this paper
• Orientable Burning Number of Graphs

  2023cites this paper
• Cup stacking in graphs

  2023cites this paper
• Burnability of double spiders and path forests

  2022cites this paper
• Burning Number for the Points in the Plane

  2022cites this paper
• Adversarial graph burning densities

  2022cites this paper
• Improved and Generalized Algorithms for Burning a Planar Point Set

  2022cites this paper
• CBAG: An Efficient Genetic Algorithm for the Graph Burning Problem

  2022cites this paper
• The burning number conjecture holds asymptotically

  2022cites this paper
• Improved pyrotechnics : Closer to the burning graph conjecture

  2021cites this paper
• Burning Numbers of t-unicyclic Graphs

  2021cites this paper
• Spread and defend infection in graphs

  2021cites this paper
• An improved bound on the burning number of graphs

  2021cites this paper
• Burning Graph Classes

  2021influential citation
• Improved Bounds for Burning Fence Graphs

  2021cites this paper
• Improved Pyrotechnics: Closer to the Burning Number Conjecture

  2021cites this paper
• Pursuit-evasion games on latin square graphs

  2021cites this paper
• Parameterized Complexity of Graph Burning

  2020cites this paper
• The Graph Burning Problem under Constrained Diffusion

  year unknowncites this paper