Article in press
Authors:
Eugene Jung Tong Jun Tong Leong
School of Mathematical Sciences, Universiti Sains Malaysia, 11800 USM, Malaysia.
email: eugeneleong@student.usm.my
Kai An Sim
School of Mathematical Sciences, Sunway University, 47500 Bandar Sunway, Malaysia
email: kaians@sunway.edu.my
Title:
Burning disjoint union of spider and path
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2025-02-27 , Revised: 2025-07-30 , Accepted: 2025-08-01 , Available online: 2025-08-29 , https://doi.org/10.7151/dmgt.2600
Abstract:
For a connected graph $G$ of order $n$, the graph burning problem models the
spread of influence in networks, with the burning number conjecture stating
$b(G)\leq \lceil \sqrt{n}\text{ }\rceil$. In 2020, Tan and Teh proposed a
stronger conjecture for trees: Every tree with $n$ leaves and order at most
$m^2+n-2$ is $m$-burnable with $m>n$. This conjecture has been proven to hold
for spiders and double spiders. However, the burning behaviour of disconnected
graphs remains unknown. Motivated by this gap, we consider a disjoint union
graph $T$ which consists of a spider with $n$ leaves and a path. In this paper,
we show a similar result such that if $T$ has order at most $m^2+n-2$ where
$m\geq n+3$, then $T$ is $m$-burnable with some exceptional cases. These results
provide some insights into how the disjoint structure of a graph influences its
burning behaviour.
Keywords:
burning number, discrete graph algorithm, disjoint union graph, social network
References:
- P. Bastide, M. Bonamy, A. Bonato, P. Charbit, S. Kamali, T. Pierron and M. Rabie, Improved pyrotechnics: Closer to the burning number conjecture, Electron. J. Combin. 30 (2023) #P4.2.
https://doi.org/10.37236/11113 - S. Bessy, A. Bonato, J. Janssen, D. Rautenbach and E. Roshanbin, Burning a graph is hard, Discrete Appl. Math. 232 (2017) 73–87.
https://doi.org/10.1016/j.dam.2017.07.016 - S. Bessy, A. Bonato, J. Janssen, D. Rautenbach and E. Roshanbin, Bounds on the burning number, Discrete Appl. Math. 235 (2018) 16–22.
https://doi.org/10.1016/j.dam.2017.09.012 - A. Bonato, A survey of graph burning, Contrib. Discrete Math. 16 (2021) 185–197.
https://doi.org/10.11575/cdm.v16i1.71194 - A. Bonato, S. English, B. Kay and D. Moghbel, Improved bounds for burning fence graphs, Graphs Combin. 37 (2021) 2761–2773.
https://doi.org/10.1007/s00373-021-02390-x - A. Bonato, K. Gunderson and A. Shaw, Burning the plane. Densities of the infinite Cartesian grid, Graphs Combin. 36 (2020) 1311–1335.
https://doi.org/10.1007/s00373-020-02182-9 - A. Bonato, J. Janssen and E. Roshanbin, How to burn a graph, Internet Math. 12 (2016) 85–100.
https://doi.org/10.1080/15427951.2015.1103339 - A. Bonato and T. Lidbetter, Bounds on the burning numbers of spiders and path-forests, Theoret. Comput. Sci. 794 (2019) 12–19.
https://doi.org/10.1016/j.tcs.2018.05.035 - S. Das, S.R. Dev, A. Sadhukhan, U.k. Sahoo and S. Sen, Burning spiders, in: Algorithms and Discrete Applied Mathematics, B.S. Panda and P.P. Goswami (Ed(s)), Lecture Notes in Comput. Sci. 10743, (Springer, Cham, 2018) 155–163.
https://doi.org/10.1007/978-3-319-74180-2_13 - S.L. Fitzpatrick and L. Wilm, Burning circulant graphs (2017).
arXiv: 1706.03106 - K. Gunderson, W. Kellough, J.D. Nir and H. Punj, Adversarial graph burning densities, Discrete Math. 348(1) (2025) 114253.
https://doi.org/10.1016/j.disc.2024.114253 - A.T. Gupta, S.A. Lokhande and K. Mondal, Burning grids and intervals, in: Algorithms and Discrete Applied Mathematics, A. Mudgal and C.R. Subramanian (Ed(s)), Lecture Notes in Comput. Sci. 12601, (Springer, Cham, 2021) 66–79.
https://doi.org/10.1007/978-3-030-67899-9_6 - M. Hiller, A.M.C.A. Koster and E. Triesch, On the burning number of p}-caterpillars, in: Graphs and Combinatorial Optimization: from Theory to Applications, C. Gentile, G. Stecca and P. Ventura (Ed(s)), AIRO Springer Ser. 5, (Springer, Cham, 2021) 145–156.
https://doi.org/10.1007/978-3-030-63072-0_12 - R. Janssen, The burning number of directed graphs: Bounds and computational complexity, Theory Appl. Graphs 7(1) (2020) 8.
https://doi.org/10.20429/tag.2020.070108 - J.M. Keil, D. Mondal and E. Moradi, Burning number for the points in the plane (2022).
arXiv: 2205.04643 - M.R. Land and L. Lu, An upper bound on the burning number of graphs, in: Algorithms and Models for the Web Graph, A. Bonato, F.C. Graham and P. Prałat (Ed(s)), Lecture Notes in Comput. Sci. 10088, (Springer, Cham, 2016) 1–8.
https://doi.org/10.1007/978-3-319-49787-7_1 - H. Liu, X. Hu and X. Hu, Burning number of caterpillars, Discrete Appl. Math. 284 (2020) 332–340.
https://doi.org/10.1016/j.dam.2020.03.062 - H. Liu, X. Hu and X. Hu, Burning numbers of path forests and spiders, Bull. Malays. Math. Sci. Soc. 44 (2021) 661–681.
https://doi.org/10.1007/s40840-020-00969-w - H. Liu, R. Zhang and X. Hu, Burning number of theta graphs, Appl. Math. Comput. 361 (2019) 246–257.
https://doi.org/10.1016/j.amc.2019.05.031 - D. Mitsche, P. Prałat and E. Roshanbin, Burning number of graph products, Theoret. Comput. Sci. 746 (2018) 124–135.
https://doi.org/10.1016/j.tcs.2018.06.036 - Y. Murakami, The burning number conjecture is true for trees without degree-$2$ vertices, Graphs Combin. 40 (2024) 82.
https://doi.org/10.1007/s00373-024-02812-6 - S. Norin and J. Turcotte, The burning number conjecture holds asymptotically, J. Combin. Theory Ser. B 168 (2024) 208–235.
https://doi.org/10.1016/j.jctb.2024.05.003 - K.A. Sim, T.S. Tan and K.B. Wong, On the burning number of generalized Petersen graphs, Bull. Malays. Math. Sci. Soc. 41 (2018) 1657–1670.
https://doi.org/10.1007/s40840-017-0585-6 - T.S. Tan and W.C. Teh, Graph burning: Tight bounds on the burning numbers of path forests and spiders, Appl. Math. Comput. 385 (2020) 125447.
https://doi.org/10.1016/j.amc.2020.125447 - T.S. Tan and W.C. Teh, Burnability of double spiders and path forests, Appl. Math. Comput. 438 (2023) 127574.
https://doi.org/10.1016/j.amc.2022.127574 - T.S. Tan and W.C. Teh, A note on graph burning of path forests, Discrete Math. Theoret. Comput. Sci. 26 (2024) 1–13.
https://doi.org/10.46298/dmtcs.12709 - R. Zhang, Y. Yu and H. Liu, Burning numbers of t-unicyclic graphs, Bull. Malays. Math. Sci. Soc. 45 (2022) 417–430.
https://doi.org/10.1007/s40840-021-01194-9
Close