From Burning Extremal Balanced Spiders Into Properties for Generalization to All Trees

Abstract Graph burning is a discrete-time deterministic process that can be interpreted as a model for spreading influence in social networks. The burning number conjecture says that the burning number of any connected graph of order $$m^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>m</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:math> is at most m and was proven to hold asymptotically recently. Since the early days, spiders have garnered a significant amount of attention. Not only were spiders shown to satisfy the conjecture, but also determining the burning numbers for spiders was an NP-complete problem. Furthermore, Tan and Teh obtained a tight upper bound beyond $$m^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>m</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:math> on the order of a spider to guarantee its burnability in m rounds, and, surprisingly, it depends only on the number of arms, with balanced spiders as exceptions for small m . Inspired by these works, we first study the largest attainable order for balanced spiders, given the number of arms and the burning number. The second half of this work lays the foundation for generalization to all trees. As highlights of this work, we obtain some principal general properties on the associated neighborhoods corresponding to any optimal burning sequence of the extremal trees with a given burning number. Finally, we apply the principles to determine the orders of the extremal trees with two branch vertices and conclude by discussing how to extend our study.