GRAPHS WITH THE BURNING NUMBERS EQUAL THREE

Wen  Li

doi:10.29121/granthaalayah.v11.i2.2023.5057

Authors

Wen Li School of Mathematics and Statistics, Qinghai Minzu University, Xining, Qinghai 810008, China https://orcid.org/0000-0001-8744-5931

DOI:

https://doi.org/10.29121/granthaalayah.v11.i2.2023.5057

Keywords:

Burning Sequence, Maximum Degree, Burning Number

Abstract [English]

The concept of burning number is inspired by the firefighting problem, which is a new measure to describe the speed of information spread. For a general non-trivial connected graph

Downloads

Download data is not yet available.

References

Alon, N., Prałat, P., and Wormald, N. (2009). Cleaning Regular Graphs with Brushes. SIAM Journal on Discrete Mathematics, 23(1), 233-250. https://doi.org/10.1137/070703053. DOI: https://doi.org/10.1137/070703053

Balogh, J., Bollobás, B., and Morris, R. (2012). Graph Bootstrap Percolation. Random Structures and Algorithms, 41(4), 413-440. https://doi.org/10.1002/rsa.20458. DOI: https://doi.org/10.1002/rsa.20458

Barghi, A., and Winkler, P. (2015). Firefighting On a Random Geometric Graph. Random Structures and Algorithms, 46(3), 466-477. https://doi.org/10.1002/rsa.20511. DOI: https://doi.org/10.1002/rsa.20511

Bessy, S., Bonato, A., Janssen, J., Rautenbach, D., and Roshanbin, E. (2017). S0166218X17304353. Bounds on the Burning Number. Discrete Applied Mathematics, 232, 73-87. https://doi.org/10.1016/j.dam.2017.07.016. DOI: https://doi.org/10.1016/j.dam.2017.07.016

Bonato, A., Janssen, J., and Roshanbin, E. (2014). Burning a Graph as a Model of Social Contagion. Lecture Notes in Computer Science, 8882, 13-22. https://doi.org/10.1007/978-3-319-13123-8_2. DOI: https://doi.org/10.1007/978-3-319-13123-8_2

Bonato, A., Janssen, J., and Roshanbin, E. (2016). How To Burn a Graph. Internet Mathematics, 12(1-2), 85-100. https://doi.org/10.1080/15427951.2015.1103339. DOI: https://doi.org/10.1080/15427951.2015.1103339

Bonato, A., Janssen, J., and Roshanbin, E. (2015). Burning a Graph is Hard. https://doi.org/10.48550/arXiv.1511.06774

Bonato, A., and Nowakowski, R. J. (2011). The Game of Cops and Robbers on Graphs. American Mathematical Society. https://doi.org/10.1090/stml/061. DOI: https://doi.org/10.1090/stml/061

Finbow, S., King, A., Macgillivray, G., and Rizzi, R. (2007). The Firefifighter Problem For Graphs of Maximum Degree Three. Discrete Mathematics, 307, 2049-2105. https://doi.org/10.1016/j.disc.2005.12.053. DOI: https://doi.org/10.1016/j.disc.2005.12.053

Finbow, S., and Macgillivray, G. (2019). The Firefighter Problem: A Survey of Results, Directions And Questions. Australasian Journal of Combinatorics, 43, 57-77.

Liu, H., Zhang, R., and Hu, X. (2019). Burning Number of Theta Graphs. Applied Mathematics and Computation, 361, 246-257. https://doi.org/10.1016/j.amc.2019.05.031. DOI: https://doi.org/10.1016/j.amc.2019.05.031

Mitsche, D., Prałat, P., and Roshanbin, E. (2018). Burning Number of Graph Products. Theoretical Computer Science, 746, 124-135. https://doi.org/10.1016/j.tcs.2018.06.036. DOI: https://doi.org/10.1016/j.tcs.2018.06.036

Mitsche, D., Prałat, P., and Roshanbin, E. (2017). Burning Graphs-A Probabilistic Perspective, Arxiv :1505.03052. Graphs and Combinatorics, 33(2), 449-471. https://doi.org/10.1007/s00373-017-1768-5. DOI: https://doi.org/10.1007/s00373-017-1768-5

Roshanbin, E. (2016). Burning A Graph as a Model of Social Contagion [Phd Thesis]. Dalhousie University.

Sim, K. A., Tan, T. S., and Wong, K. B. (2018). On the Burning Number of Generalized Petersen Graphs. Bulletin of the Malaysian Mathematical Sciences Society, 41(3), 1657-1670. https://doi.org/10.1007/s40840-017-0585-6. DOI: https://doi.org/10.1007/s40840-017-0585-6