Burning the plane. Densities of the infinite Cartesian grid

DOI10.1007/S00373-020-02182-9MaRDI QIDQ2227973zbMATH OpenOpenAlexFDO

Authors Karen Gunderson, Amy Shaw, Anthony Bonato

Publication date 16 February 2021

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

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

zbMATH Keywords

densityextremal combinatoricsgraph burning

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Infinite graphs (05C63)

Abstract: Graph burning is a discrete-time process on graphs, where vertices are sequentially burned, and burned vertices cause their neighbours to burn over time. We consider extremal properties of this process in the new setting where the underlying graph is also changing at each time-step. The main focus is on the possible densities of burning vertices when the sequence of underlying graphs are growing grids in the Cartesian plane, centred at the origin. If the grids are of height and width $2cn+1$ at time $n$, then all values in $left[frac12c^2,1ight]$ are possible densities for the burned set. For faster growing grids, we show that there is a threshold behaviour: if the size of the grids at time $n$ is $omega(n^{3/2})$, then the density of burned vertices is always $0$, while if the grid sizes are $Theta(n^{3/2})$, then positive densities are possible. Some extensions to lattices of arbitrary but fixed dimension are also considered.

Recommendations

• Improved bounds for burning fence graphs
• Burning number of graph products
• Burning and \(w\)-burning of geometric graphs
• Firefighting on geometric graphs with density bounds.
• Average firefighting on infinite grids

Cites work

• An upper bound on the burning number of graphs
• Approximation algorithms for graph burning
• Bounds on the burning number
• Bounds on the burning numbers of spiders and path-forests
• Burning a graph as a model of social contagion
• Burning a graph is hard
• Burning graphs: a probabilistic perspective
• Contact interactions on a lattice
• How to Burn a Graph
• scientific article; zbMATH DE number 5454133 (Why is no real title available?)
• scientific article; zbMATH DE number 3463051 (Why is no real title available?)
• scientific article; zbMATH DE number 3231627 (Why is no real title available?)
• Maximal percolation time in hypercubes under 2-bootstrap percolation
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• On slowly percolating sets of minimal size in bootstrap percolation
• The Firefighter problem: a survey of results, directions and questions
• The surviving rate of a graph for the firefighter problem

Cited in

(12)

• Improved bounds for burning fence graphs
• Surviving rate of graphs and firefighter problem
• Parameterized complexity of graph burning
• A survey of graph burning
• Firefighting on geometric graphs with density bounds.
• APX-hardness and approximation for the \(k\)-burning number problem
• APX-hardness and approximation for the \(k\)-burning number problem
• Parameterized Complexity of Graph Burning
• Adversarial graph burning densities
• Burning disjoint union of spider and path
• Burn and win
• Between burning and cooling: liminal burning on graphs

This page was built for publication: Burning the plane. Densities of the infinite Cartesian grid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2227973)