Burning graphs: a probabilistic perspective
From MaRDI portal
Publication:2014226
DOI10.1007/S00373-017-1768-5zbMATH Open1368.05134arXiv1505.03052OpenAlexW2964242347MaRDI QIDQ2014226FDOQ2014226
Authors: Paweł Prałat, Elham Roshanbin, D. Mitsche 
Publication date: 10 August 2017
Published in: Graphs and Combinatorics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1505.03052
Recommendations
Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Graph operations (line graphs, products, etc.) (05C76)
Cites Work
- Random Geometric Graphs
- Title not available (Why is that?)
- Some remarks on cops and drunk robbers
- Random graphs.
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- The Firefighter problem: a survey of results, directions and questions
- Sparse graphs are not flammable
- Cleaning random graphs with brushes
- Cleaning regular graphs with brushes
- Cleaning random \(d\)-regular graphs with brooms
- The longest edge of the random minimal spanning tree
- Cops and invisible robbers: the cost of drunkenness
- Graphs with average degree smaller than \(\frac{30}{11}\) burn slowly
- Monotone properties of random geometric graphs have sharp thresholds
- Bounds on the burning number
- An upper bound on the burning number of graphs
- Burning a graph is hard
- Burning a graph as a model of social contagion
- How to Burn a Graph
- On the relation between graph distance and Euclidean distance in random geometric graphs
- On the Push\&Pull protocol for rumour spreading (extended abstract)
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
- Burning two worlds
- How to Burn a Graph
- On the burning number of generalized Petersen graphs
- Parameterized Complexity of Graph Burning
- Adversarial graph burning densities
- Burning graph classes
- Parameterized complexity of graph burning
- 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 Numbers of Barbells
- Burning a graph is hard
- 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)
