Burning the Plane
- PDF / 398,863 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 17 Downloads / 202 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Burning the Plane Densities of the Infinite Cartesian Grid Anthony Bonato1 • Karen Gunderson2 • Amy Shaw2 Received: 20 June 2018 / Revised: 21 April 2020 Ó Springer Japan KK, part of Springer Nature 2020
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 1 time n, then all values in 2c2 ; 1 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 xðn3=2 Þ, then the density of burned vertices is always 0, while if the grid sizes are Hðn3=2 Þ, then positive densities are possible. Some extensions to lattices of arbitrary but fixed dimension are also considered. Keywords Graph burning Density Extremal combinatorics
Mathematics Subject Classification 05C35 05C42 05C63
AB and KG supported by NSERC Discovery grants. & Karen Gunderson [email protected] Anthony Bonato [email protected] 1
Department of Mathematics, Ryerson University, Toronto, ON M5B 2K3, Canada
2
Department of Mathematics, University of Manitoba, Winnipeg, MB R3T 2N2, Canada
123
Graphs and Combinatorics
1 Introduction Numerous recent works have analyzed the spread of social contagion in real-word networks. As an example, [17] demonstrated that emotional states can be transferred to others on Facebook without direct interaction between people and in the complete absence of nonverbal cues. Graph burning is a new, discrete-time process that measures how prone a network is to fast social contagion. The input of the process is an undirected finite graph and at each step, vertices are either burning (also called burned) or not. Initially, a single vertex, called an activator, is burning and in each subsequent round, every neighbour of a burning vertex becomes burned and a fire is ignited at a new activator which is also burning. The process is complete once all vertices are burning. In this paper, the focus is on the behaviour of the process when the sequence of activators is chosen deterministically to minimize the number of rounds. The burning number of a graph G is the minimum number of rounds it takes for all vertices to be burned in G. Bonato et al. [5, 6, 22] first introduced the burning process, found bounds, and characterized the burning number for various graph classes. It was proved by Bessy et al. in [4] that for a connected graph of order n, the burning number is at most pffiffi pffiffiffi pffiffiffi 2d ne 1, and this bound was improved by Land and Lu [18] to 26 n. In [4], Bessy et al. conjectured that the burning number of a conne
Data Loading...
