Abstract: In this paper, we study a graph parameter that was recently introduced, the burning number, focusing on a few probabilistic aspects of the problem. The original burning number is revisited and analyzed for binomial random graphs G(n,p), random geometric graphs, and the Cartesian product of paths. Moreover, new variants of the burning number are introduced in which a burning sequence of vertices is selected according to some probabilistic rules. We analyze these new graph parameters for paths.
Recommendations
Cites work
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- An upper bound on the burning number of graphs
- Bounds on the burning number
- Burning a graph as a model of social contagion
- Burning a graph is hard
- Cleaning random \(d\)-regular graphs with brooms
- Cleaning random graphs with brushes
- Cleaning regular graphs with brushes
- Cops and invisible robbers: the cost of drunkenness
- Graphs with average degree smaller than \(\frac{30}{11}\) burn slowly
- How to Burn a Graph
- Monotone properties of random geometric graphs have sharp thresholds
- On the Push\&Pull protocol for rumour spreading (extended abstract)
- On the relation between graph distance and Euclidean distance in random geometric graphs
- Random Geometric Graphs
- Random graphs.
- Some remarks on cops and drunk robbers
- Sparse graphs are not flammable
- The Firefighter problem: a survey of results, directions and questions
- The longest edge of the random minimal spanning tree
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
Cited in
(22)- Burnability of double spiders and path forests
- Surviving rate of graphs and firefighter problem
- Burning graph classes
- Bounds on the burning numbers of spiders and path-forests
- Parameterized complexity of graph burning
- Burning number of caterpillars
- Parameterized Complexity of Graph Burning
- Improved bounds for burning fence graphs
- Burning Numbers of Barbells
- Burning two worlds
- A survey of graph burning
- Graph burning: tight bounds on the burning numbers of path forests and spiders
- Burning numbers of \(t\)-unicyclic graphs
- The burning numbers of generalized Peterson graphs \(P(n, 1)\) and \(P(n, 2)\)
- Burning numbers of path forests and spiders
- How to Burn a Graph
- On the burning number of generalized Petersen graphs
- Burning a graph is hard
- Burning number of theta graphs
- Burning number of graph products
- Adversarial graph burning densities
- Burning the plane. Densities of the infinite Cartesian grid
This page was built for publication: Burning graphs: a probabilistic perspective
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2014226)
