Improved Bounds for Burning Fence Graphs

2019/11/04 by Anthony Bonato, Bonato, Anthony, Sean English +5 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1911.01342

arxiv created 2019/11/04 · arxiv updated 2019/11/05

Abstract

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 × n Cartesian grid graphs, written G_m,n. For m = ω(√(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(√(n)), which we refer to as fence graphs. We provide new explicit bounds on the burning number of fence graphs G_c√(n),n, where c > 0.

Cited by

• Between burning and cooling: liminal burning on graphs

Related

• An Upper Bound on Burning Number of Graphs
• The Graph Burning Conjecture is true for trees without degree-2 vertices
• Bounds on the Burning Number
• New heuristics for burning graphs
• Approximation Algorithms for Graph Burning