Structural Properties Of Extremal Trees, Balanced Spiders, And Path Forests With Respect To Burning Number
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 remarkabl...
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2024
|
| Subjects: | |
| Online Access: | http://eprints.usm.my/62442/ http://eprints.usm.my/62442/1/24%20Pages%20from%20EUGENE%20LEONG%20JUN%20TONG.pdf |
| Summary: | 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. |
|---|