How to Burn a Graph
From MaRDI portal
Abstract: We introduce a new graph parameter called the burning number, inspired by contact processes on graphs such as graph bootstrap percolation, and graph searching paradigms such as Firefighter. The burning number measures the speed of the spread of contagion in a graph; the lower the burning number, the faster the contagion spreads. We provide a number of properties of the burning number, including characterizations and bounds. The burning number is computed for several graph classes, and is derived for the graphs generated by the Iterated Local Transitivity model for social networks.
Recommendations
Cites work
- A survey of Nordhaus-Gaddum type relations
- Automata, Languages and Programming
- Burning a graph is hard
- Cleaning regular graphs with brushes
- Epidemic Spreading With External Agents
- Firefighting on a random geometric graph
- Graph bootstrap percolation
- scientific article; zbMATH DE number 6474901 (Why is no real title available?)
- scientific article; zbMATH DE number 5485445 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- Information diffusion on the iterated local transitivity model of online social networks
- Models of online social networks
- On Complementary Graphs
- The firefighter problem for graphs of maximum degree three
- The Firefighter problem: a survey of results, directions and questions
- The game of cops and robbers on graphs
- The small-world phenomenon: an algorithmic perspective
Cited in
(63)- Bounds on the burning number
- Burning number of graph products
- Burning graphs: a probabilistic perspective
- Burning numbers of path forests and spiders
- Improved bounds for burning fence graphs
- On the burning number of \(p\)-caterpillars
- Burning numbers of \(t\)-unicyclic graphs
- Burnability of double spiders and path forests
- Surviving rate of graphs and firefighter problem
- Burning graph classes
- Parameterized complexity of graph burning
- A new model and algorithms in firefighting theory
- Burning the plane. Densities of the infinite Cartesian grid
- The generalized burning number of graphs
- Burning number of theta graphs
- Bounds on the burning numbers of spiders and path-forests
- Burning a graph is hard
- Graph burning: tight bounds on the burning numbers of path forests and spiders
- Burning a graph as a model of social contagion
- Burning two worlds
- A survey of graph burning
- The burning number of directed graphs: bounds and computational complexity
- The damage number of a graph
- APX-hardness and approximation for the \(k\)-burning number problem
- APX-hardness and approximation for the \(k\)-burning number problem
- Selection of activators in finding the burning number
- Parameterized Complexity of Graph Burning
- Burning and \(w\)-burning of geometric graphs
- Graph burning and non-uniform \(k\)-centers for small treewidth
- Burn and win
- Improved pyrotechnics: closer to the burning number conjecture
- Burning Numbers of Barbells
- The burning number conjecture holds asymptotically
- Orientable burning number of graphs
- The burning number conjecture is true for trees without degree-2 vertices
- Spanning caterpillar in biconvex bipartite graphs
- Adversarial graph burning densities
- Burning number of Jahangir graphs
- The burning game on graphs
- Burning sufficiently large p-caterpillars for a fixed p
- Burning disjoint union of spider and path
- Burning path-like and clique-like graphs
- Hypergraph burning, matchings, and zero forcing
- Homology of graph burnings
- From burning extremal balanced spiders into properties for generalization to all trees
- How to burn a Latin square
- Burn and win
- Information dissemination and confusion in signed networks
- Approximation algorithms for the graph burning on cactus and directed trees
- A note on graph burning of path forests
- Graphs with burning number three
- Orientable burning number of graphs
- Burning random trees
- On the burning number of generalized Petersen 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
- The generalized burning number of caterpillars
- On the burning number of the generalized Heawood graphs
- Deterministic approximation algorithm for graph burning
- Burning number of caterpillars
- The iterated local model for social networks
- Burning grids and intervals
This page was built for publication: How to Burn a Graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5856432)
