Publication: Structural Properties Of Extremal Trees, Balanced Spiders, And Path Forests With Respect To Burning Number
Loading...
Date
2024-04
Authors
Eugene Leong Jun, Tong
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Graph burning is a discrete-time deterministic graph process that can be interpreted as a model for spread of influence in social networks. Bonato et al. conjectured in 2016 that for any connected graph of order N2, the burning number is at most N. This conjecture remains open, although remarkable progress has been achieved lately. By noting that the burning number of any connected graph is the minimum burning number of its spanning trees, our work focuses on identifying extremal trees in the sense that each tree attains the largest possible order among homeomorphic trees with a given burning number. The study initiates with finding the tight bounds on the orders of path forests, balanced path forests, spiders, and balanced spiders when the burning number is fixed. The tight bounds for a given class of graphs render the possible range of burning numbers for any given graph in the class. Upon generalizing, we obtain some general properties on the associated neighbourhoods corresponding to any optimal burning sequence of any extremal tree. Based on that, we propose a new framework consisting of admissible sequences over any homeomorphically irreducible tree such that any extremal tree with a given burning number can be induced by some admissible sequence in some sense. Utilising the properties of admissible sequences corresponding to extremal trees, we obtain the extremal trees with any given burning number for the case of four branch vertices.
Description
Keywords
Structural Properties Of Extremal Trees