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)- Burning number of theta graphs
- Bounds on the burning numbers of spiders and path-forests
- Surviving rate of graphs and firefighter problem
- A survey of graph burning
- On the burning number of generalized Petersen graphs
- Burning two worlds
- How to Burn a Graph
- Parameterized Complexity of Graph Burning
- Burning graph classes
- Parameterized complexity of graph burning
- Adversarial graph burning densities
- The burning numbers of generalized Peterson graphs \(P(n, 1)\) and \(P(n, 2)\)
- Improved bounds for burning fence graphs
- Burning numbers of \(t\)-unicyclic graphs
- Burning the plane. Densities of the infinite Cartesian grid
- Burning number of caterpillars
- Burning a graph is hard
- Burning Numbers of Barbells
- Graph burning: tight bounds on the burning numbers of path forests and spiders
- Burning number of graph products
- Burning numbers of path forests and spiders
- Burnability of double spiders and path forests
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)
