Burning numbers of path forests and spiders. (English) Zbl 1462.05254
Summary: Graph burning is a deterministic discrete-time graph process that can be interpreted as a model for the spread of influence in social networks. The burning number of a graph \(G\) is the minimum number of steps in a graph burning process for \(G\). It is shown that the graph burning problem is NP-complete even for trees and path forests. In this paper, we first determine the burning numbers of path forests with at most three components and then use these results to determine the burning numbers of all spiders with three arms.
MSC:
| 05C57 | Games on graphs (graph-theoretic aspects) |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 91A43 | Games involving graphs |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 91D30 | Social networks; opinion dynamics |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | Alon, N.; Feldman, M.; Procaccia, AD; Tennenholtz, M., A note on competitive diffusion through social networks, Inf. Process. Lett., 110, 221-225 (2010) · Zbl 1197.91057 · doi:10.1016/j.ipl.2009.12.009 |
| [2] | Balogh, J.; Bollobás, B.; Morris, R., Graph bootstrap percolation, Random Struct. Algorithms, 41, 413-440 (2012) · Zbl 1279.68243 · doi:10.1002/rsa.20458 |
| [3] | Bessy, S.; Bonato, A.; Janssen, J.; Rautenbach, D.; Roshanbin, E., Burning a graph is hard, Discrete Appl. Math., 232, 73-87 (2017) · Zbl 1372.05214 · doi:10.1016/j.dam.2017.07.016 |
| [4] | Bessy, S.; Bonato, A.; Janssen, J.; Rautenbach, D.; Roshanbin, E., Bounds on the burning number, Discrete Appl. Math., 235, 16-22 (2018) · Zbl 1375.05192 · doi:10.1016/j.dam.2017.09.012 |
| [5] | Bonato, A.; Janssen, J.; Roshanbin, E., Burning a graph as a model of social contagion, Lect. Notes Comput. Sci., 8882, 13-22 (2014) · Zbl 1342.05154 · doi:10.1007/978-3-319-13123-8_2 |
| [6] | Bonato, A.; Janssen, J.; Roshanbin, E., How to burn a graph, Internet Math., 1-2, 85-100 (2016) · Zbl 1461.05193 · doi:10.1080/15427951.2015.1103339 |
| [7] | Bonato, A.; Lidbetter, T., Bounds on the burning numbers of spiders and path-forests, Theoret. Comput. Sci., 794, 12-19 (2019) · Zbl 1433.05297 · doi:10.1016/j.tcs.2018.05.035 |
| [8] | Bonato, A.; Prałat, P., Graph Searching Games and Probabilistic Methods (2017), London: CRC Press, London · Zbl 1398.91002 · doi:10.1201/9781315212135 |
| [9] | Finbow, S.; MacGillivray, G., The Firefighter problem: a survey of results, directions and questions, Australas. J. Comb., 43, 57-77 (2009) · Zbl 1179.05112 |
| [10] | Fitzpatrick, S.L., Wilm, L.: Burning circulant graphs, arXiv:1706.03106 |
| [11] | Haynes, TW; Hedetniemi, ST; Slater, PJ, Fundamentals of Domination in Graphs (1998), New York: Marcel Dekker, New York · Zbl 0890.05002 |
| [12] | Kramer, ADI; Guillory, JE; Hancock, JT, Experimental evidence of massive-scale emotional contagion through social networks, Proc. Nat. Acad. Sci. USA, 111, 8788-8790 (2014) · doi:10.1073/pnas.1320040111 |
| [13] | Land, M.R., Lu, L.Y.: An upper bound on the burning number of graphs, In: Bonato, A., Graham, F., Pralat P. (eds) Algorithms and Models for the Web Graph. WAW 2016, Lecture Notes in Computer Science, vol. 10088. Springer, Cham (2016) · Zbl 1398.68405 |
| [14] | Liu, H.Q., Hu, X.J., Hu, X.L.: Burning number of caterpillars. Discrete Appl. Math. (2020). doi:10.1016/j.dam.2020.03.062 · Zbl 1443.05149 |
| [15] | Liu, HQ; Zhang, RT; Hu, XL, Burning number of theta graphs, Appl. Math. Comput., 361, 246-257 (2019) · Zbl 1422.65397 · doi:10.1016/j.cam.2019.04.024 |
| [16] | Mitsche, D.; Prałat, P.; Roshanbin, E., Burning graphs: a probabilistic perspective, Graphs Comb., 33, 449-471 (2017) · Zbl 1368.05134 · doi:10.1007/s00373-017-1768-5 |
| [17] | Mitsche, D.; Prałat, P.; Roshanbin, E., Burning number of graph products, Theoret. Comput. Sci., 746, 124-135 (2018) · Zbl 1401.05257 · doi:10.1016/j.tcs.2018.06.036 |
| [18] | Roshanbin, E.: Burning a graph as a model of social contagion, Ph.D. Thesis, Dalhousie University (2016) · Zbl 1342.05154 |
| [19] | Sim, KA; Tan, TS; Wong, KB, On the burning number of generalized Petersen graphs, Bull. Malays. Math. Sci. Soc., 41, 1657-1670 (2018) · Zbl 1393.05249 · doi:10.1007/s40840-017-0585-6 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
