Graph Burning On Large p-Caterpillars

2024/12/17 by Cox, Danielle, Messinger, M. E., Ojakian, Kerry
#05C57 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2412.12970

Abstract

Graph burning models the spread of information or contagion in a graph. At each time step, two events occur: neighbours of already burned vertices become burned, and a new vertex is chosen to be burned. The big conjecture is known as the \it burning number conjecture: for any connected graph on n vertices, all n vertices can be burned after at most \lceil √(n) \rceil time steps. It is well-known that to prove the conjecture, it suffices to prove it for trees. We prove the conjecture for sufficiently large p-caterpillars.

Related

• On the Burning Number of p-Caterpillars
• The Graph Burning Conjecture is true for trees without degree-2 vertices
• Graph Burning: Tight Bounds on the Burning Numbers of Path Forests and Spiders
• Burning Two Worlds: Algorithms for Burning Dense and Tree-like Graphs
• New heuristics for burning graphs