Improved Bounds for Burning Fence Graphs
2021
Graph burning studies how fast a contagion, modeled as a set of fires, spreads in a graph. The burning process takes place in synchronous, discrete rounds. In each round, a fire breaks out at a vertex, and the fire spreads to all vertices that are adjacent to a burning vertex. The burning number of a graph G is the minimum number of rounds necessary for each vertex of G to burn. We consider the burning number of the $$m \times n$$
Cartesian grid graphs, written $$G_{m,n}$$
. For $$m = \omega (\sqrt{n})$$
, the asymptotic value of the burning number of $$G_{m,n}$$
was determined, but only the growth rate of the burning number was investigated in the case $$m = O(\sqrt{n})$$
, which we refer to as fence graphs. We provide new explicit bounds on the burning number of fence graphs $$G_{c\sqrt{n},n}$$
, where $$c > 0$$
.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
14
References
0
Citations
NaN
KQI