Burning graphs: a probabilistic perspective

DOI10.1007/s00373-017-1768-5zbMath1368.05134arXiv1505.03052OpenAlexW2964242347MaRDI QIDQ2014226

Paweł Prałat, Elham Roshanbin, Dieter Mitsche

Publication date: 10 August 2017

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1505.03052

zbMATH Keywords

random graphsrandom geometric graphsburning numberCartesian product of paths

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Graph operations (line graphs, products, etc.) (05C76)

Related Items

Surviving rate of graphs and firefighter problem ⋮ A survey of graph burning ⋮ Burning graph classes ⋮ Parameterized complexity of graph burning ⋮ Graph burning: tight bounds on the burning numbers of path forests and spiders ⋮ Burning a graph is hard ⋮ Burning the plane. Densities of the infinite Cartesian grid ⋮ Burning Two Worlds ⋮ Parameterized Complexity of Graph Burning ⋮ Burning numbers of path forests and spiders ⋮ Burning number of graph products ⋮ Burning number of theta graphs ⋮ On the burning number of generalized Petersen graphs ⋮ Improved bounds for burning fence graphs ⋮ Burning numbers of \(t\)-unicyclic graphs ⋮ Burning number of caterpillars ⋮ Bounds on the burning numbers of spiders and path-forests ⋮ Burnability of double spiders and path forests

Cites Work

• Cops and invisible robbers: the cost of drunkenness
• Cleaning random \(d\)-regular graphs with brooms
• Graphs with average degree smaller than \(\frac{30}{11}\) burn slowly
• The longest edge of the random minimal spanning tree
• Bounds on the burning number
• Some remarks on cops and drunk robbers
• An upper bound on the burning number of graphs
• Burning a graph is hard
• Monotone properties of random geometric graphs have sharp thresholds
• On the Push&Pull Protocol for Rumour Spreading
• On the relation between graph distance and Euclidean distance in random geometric graphs
• Burning a Graph as a Model of Social Contagion
• Random Geometric Graphs
• Cleaning Regular Graphs with Brushes
• Sparse Graphs Are Not Flammable
• How to Burn a Graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item