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 |
| _version_ | 1848884987038793728 |
|---|---|
| author | Eugene Leong Jun, Tong |
| author_facet | Eugene Leong Jun, Tong |
| author_sort | Eugene Leong Jun, Tong |
| building | USM Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-15T19:15:26Z |
| format | Thesis |
| id | usm-62442 |
| institution | Universiti Sains Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-15T19:15:26Z |
| publishDate | 2024 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | usm-624422025-06-11T08:46:39Z http://eprints.usm.my/62442/ Structural Properties Of Extremal Trees, Balanced Spiders, And Path Forests With Respect To Burning Number Eugene Leong Jun, Tong QA1 Mathematics (General) 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. 2024-04 Thesis NonPeerReviewed application/pdf en http://eprints.usm.my/62442/1/24%20Pages%20from%20EUGENE%20LEONG%20JUN%20TONG.pdf Eugene Leong Jun, Tong (2024) Structural Properties Of Extremal Trees, Balanced Spiders, And Path Forests With Respect To Burning Number. Masters thesis, Perpustakaan Hamzah Sendut. |
| spellingShingle | QA1 Mathematics (General) Eugene Leong Jun, Tong Structural Properties Of Extremal Trees, Balanced Spiders, And Path Forests With Respect To Burning Number |
| title | Structural Properties Of Extremal
Trees, Balanced Spiders, And Path
Forests With Respect To Burning
Number |
| title_full | Structural Properties Of Extremal
Trees, Balanced Spiders, And Path
Forests With Respect To Burning
Number |
| title_fullStr | Structural Properties Of Extremal
Trees, Balanced Spiders, And Path
Forests With Respect To Burning
Number |
| title_full_unstemmed | Structural Properties Of Extremal
Trees, Balanced Spiders, And Path
Forests With Respect To Burning
Number |
| title_short | Structural Properties Of Extremal
Trees, Balanced Spiders, And Path
Forests With Respect To Burning
Number |
| title_sort | structural properties of extremal
trees, balanced spiders, and path
forests with respect to burning
number |
| topic | QA1 Mathematics (General) |
| url | http://eprints.usm.my/62442/ http://eprints.usm.my/62442/1/24%20Pages%20from%20EUGENE%20LEONG%20JUN%20TONG.pdf |