A survey of graph burning
From MaRDI portal
Abstract: 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.
Recommendations
Cites work
- An upper bound on the burning number of graphs
- Approximation algorithms for graph burning
- Bounds on the burning numbers of spiders and path-forests
- Burning a graph as a model of social contagion
- Burning a graph is hard
- Burning graphs: a probabilistic perspective
- Burning number of caterpillars
- Burning number of theta graphs
- Burning spiders
- Burning the plane. Densities of the infinite Cartesian grid
- Burning two worlds
- Graph burning: tight bounds on the burning numbers of path forests and spiders
- How to Burn a Graph
- scientific article; zbMATH DE number 6474901 (Why is no real title available?)
- scientific article; zbMATH DE number 5595162 (Why is no real title available?)
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- Improved bounds for burning fence graphs
- Parameterized algorithms for Graph Burning problem
- Parameterized Complexity of Graph Burning
- Random graphs.
- The burning number of directed graphs: bounds and computational complexity
- The design of approximation algorithms
- The Firefighter problem: a survey of results, directions and questions
- The game of cops and robbers on graphs
- Throttling for the game of cops and robbers on graphs
- Tree-decompositions with bags of small diameter
Cited in
(39)- Burning number of graph products
- Burning graphs: a probabilistic perspective
- Improved bounds for burning fence graphs
- Burning numbers of \(t\)-unicyclic graphs
- Burnability of double spiders and path forests
- Burning graph classes
- Parameterized complexity of graph burning
- Burning a graph as a model of social contagion
- Burning two worlds
- scientific article; zbMATH DE number 5016646 (Why is no real title available?)
- How to Burn a Graph
- APX-hardness and approximation for the \(k\)-burning number problem
- Selection of activators in finding the burning number
- Improved and generalized algorithms for burning a planar point set
- Groups burning: analyzing spreading processes in community-based networks
- Burning and \(w\)-burning of geometric graphs
- Burn and win
- Improved pyrotechnics: closer to the burning number conjecture
- Burning Numbers of Barbells
- Cup stacking in graphs
- The burning number conjecture holds asymptotically
- Orientable burning number of graphs
- The burning number conjecture is true for trees without degree-2 vertices
- Burning Hamming graphs
- Adversarial graph burning densities
- Graph burning in community-based networks
- Upper bounds and approximation results for the \(k\)-slow burning problem
- The burning game on graphs
- Burning sufficiently large p-caterpillars for a fixed p
- Burning disjoint union of spider and path
- Hypergraph burning, matchings, and zero forcing
- Alon's transmitting problem and multicolor Beck-Spencer Lemma
- From burning extremal balanced spiders into properties for generalization to all trees
- How to burn a Latin square
- A note on graph burning of path forests
- Orientable burning number of graphs
- A row generation algorithm for finding optimal burning sequences of large graphs
- Between burning and cooling: liminal burning on graphs
- Extending graph burning to hypergraphs
This page was built for publication: A survey of graph burning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4986283)
