Improved bounds for burning fence graphs

DOI10.1007/S00373-021-02390-XMaRDI QIDQ2053737zbMATH OpenOpenAlexFDO

Authors Sean English, Bill Kay, Daniel Moghbel, Anthony Bonato

Publication date 30 November 2021

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

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

zbMATH Keywords

boundsburning numberCartesian gridsfence graphs

Mathematics Subject Classification ID

Graph operations (line graphs, products, etc.) (05C76) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

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 $mimesn$ Cartesian grid graphs, written $G_{m,n}$. For $m=omega(sqrtn)$, 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(sqrtn)$, which we refer to as fence graphs. We provide new explicit bounds on the burning number of fence graphs $G_{csqrtn,n}$, where $c>0$.

Recommendations

• Bounds on the burning number
• An upper bound on the burning number of graphs
• Graph burning: tight bounds on the burning numbers of path forests and spiders
• A survey of graph burning
• How to Burn a Graph

Cites work

• A survey of graph burning
• An upper bound on the burning number of graphs
• Approximation algorithms for graph burning
• Bounds on the burning number
• Burning a graph as a model of social contagion
• Burning a graph is hard
• Burning graphs: a probabilistic perspective
• Burning number of graph products
• Burning the plane. Densities of the infinite Cartesian grid
• Burning two worlds
• How to Burn a Graph

Cited in

(7)

• Parameterized complexity of graph burning
• Burning the plane. Densities of the infinite Cartesian grid
• A survey of graph burning
• Burning disjoint union of spider and path
• Burn and win
• A row generation algorithm for finding optimal burning sequences of large graphs
• Between burning and cooling: liminal burning on graphs

This page was built for publication: Improved bounds for burning fence graphs

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