Research ArticleOpen AccessGoogle Scholar indexed
The Independent Cascade Graph Burning for Operation Graphs
Department of Mathematics, Qinghai Minzu University, Xining, China
Department of Mathematics, Qinghai Minzu University, Xining, China
Department of Mathematics, Qinghai Minzu University, Xining, China
- 1 Department of Mathematics, Qinghai Minzu University, Xining, China
- 2 Department of Mathematics, Qinghai Minzu University, Xining, China
- 3 Department of Mathematics, Qinghai Minzu University, Xining, China
Applied Mathematics·Volume 16 (2025)·Pages 867–876·Published 22 December 2025·DOI10.4236/am.2025.1612045
Copy link · social · email
Abstract
Graph burning is a model to describe the spread of social influence. In 2023, Song et al. proposed the Independent Cascade Graph Burning model, where a vertex v can be burned by its burning neighbors u and the influence that u gives to v is larger than a given threshold β . The minimum number of time steps that can be chosen as rounds to burn the whole graph G with the Independent Cascade Graph Burning model called the IC burning number b β ( G ) . In this paper, we determined the IC burning number for some graphs and operation graphs.
KeywordsIC Burning NumberBinary TreeSpiderSunflower Graph
- Bonato, A., Janssen, J. and Roshanbin, E. (2014) Burning a Graph as a Model of Social Contagion. In: Bonato, A., Graham, F. and Prałat, P., Eds., Lecture Notes in Computer Science , Springer International Publishing, 13-22. https://doi.org/10.1007/978-3-319-13123-8_2
- Bessy, S., Bonato, A., Janssen, J., Rautenbach, D. and Roshanbin, E. (2017) Burning a Graph Is Hard. Discrete Applied Mathematics , 232, 73-87. https://doi.org/10.1016/j.dam.2017.07.016
- Bonato, A. and Lidbetter, T. (2019) Bounds on the Burning Numbers of Spiders and Path-Forests. Theoretical Computer Science , 794, 12-19. https://doi.org/10.1016/j.tcs.2018.05.035
- Liu, H., Hu, X. and Hu, X. (2021) Burning Numbers of Path Forests and Spiders. Bul letin of the Malaysian Mathematical Sciences Society , 44, 661-681. https://doi.org/10.1007/s40840-020-00969-w
- Sim, K.A., Tan, T.S. and Wong, K.B. (2017) On the Burning Number of Generalized Petersen Graphs. Bulletin of the Malaysian Mathematical Sciences Society , 41, 1657-1670. https://doi.org/10.1007/s40840-017-0585-6
- Liu, H., Zhang, R. and Hu, X. (2019) Burning Number of Theta Graphs. Applied Math ematics and Computation , 361, 246-257. https://doi.org/10.1016/j.amc.2019.05.031
- Liu, H., Hu, X. and Hu, X. (2020) Burning Number of Caterpillars. Discrete Applied Mathematics , 284, 332-340. https://doi.org/10.1016/j.dam.2020.03.062
- Bonato, A., English, S., Kay, B. and Moghbel, D. (2021) Improved Bounds for Burning Fence Graphs. Graphs and Combinatorics , 37, 2761-2773. https://doi.org/10.1007/s00373-021-02390-x
- Bonato, A. (2021) A Survey of Graph Burning. Contributions to Discrete Mathematics , 16, 185-197. https://doi.org/10.55016/ojs/cdm.v16i1.71194
- Li, Y., Qin, X. and Li, W. (2021) The Generalized Burning Number of Graphs. Applied Mathematics and Computation , 411, Article 126306. https://doi.org/10.1016/j.amc.2021.126306
- Song, J., Qi, X. and Cao, Z. (2023) An Independent Cascade Model of Graph Burning. Symmetry , 15, Article 1527. https://doi.org/10.3390/sym15081527
- Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Macmillan and Elsevier.
- Bonato, A., Janssen, J. and Roshanbin, E. (2016) How to Burn a Graph. Internet Mat hematics , 12, 85-100. https://doi.org/10.1080/15427951.2015.1103339