Burning graphs: a probabilistic perspective. (English) Zbl 1368.05134
Summary: In this paper, we study a graph parameter that was recently introduced, the burning number, focusing on a few probabilistic aspects of the problem. The original burning number is revisited and analyzed for binomial random graphs \({\mathcal {G}}(n,p)\), random geometric graphs, and the Cartesian product of paths. Moreover, new variants of the burning number are introduced in which a burning sequence of vertices is selected according to some probabilistic rules. We analyze these new graph parameters for paths.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C76 | Graph operations (line graphs, products, etc.) |
| 60C05 | Combinatorial probability |
References:
| [1] | Acan, H., Collevecchio, A., Mehrabian, A., Wormald, N.: On the push and pull protocol for rumour spreading. PODC 2015 (to appear) · Zbl 1333.68037 |
| [2] | Alder, J., Lev, E.: Bootstrap percolation: visualizations and applications. Braz. J. Phys. 33, 641-644 (2003) · doi:10.1590/S0103-97332003000300031 |
| [3] | Alon, N., Prałat, P., Wormald, N.: Cleaning regular graphs with brushes. SIAM J. Discrete Math. 23, 233-250 (2008) · Zbl 1187.05066 · doi:10.1137/070703053 |
| [4] | Alon, N., Spencer, J.: The Probabilistic Method, 3rd edn. Wiley, New York (2008) · Zbl 1148.05001 · doi:10.1002/9780470277331 |
| [5] | Bollobás, B.: Random Graphs. Cambridge University Press, Cambridge (2001) · Zbl 0979.05003 · doi:10.1017/CBO9780511814068 |
| [6] | Bessy, S., Bonato, A., Janssen, J., Rautenbach, D., Roshanbin, E.: Bounds on the Burning Number. Submitted (2016) · Zbl 1375.05192 |
| [7] | Bessy, S., Bonato, A., Janssen, J., Rautenbach, D., Roshanbin, E.: Burning a Graph is Hard. Submitted (2016) · Zbl 1372.05214 |
| [8] | Bonato, A., Janssen, J., Roshanbin, E.: How to burn a graph. Int. Math. 1-2, 85-100 (2016) · Zbl 1461.05193 |
| [9] | Diaz, J., Mitsche, D., Perarnau, G., Perez-Gimenez, X.: On the relation between graph distance and Euclidean distance in random geometric graphs. Adv. Appl. Probab. 48(3), 848-864 (2016) · Zbl 1348.05188 · doi:10.1017/apr.2016.31 |
| [10] | Finbow, S., MacGillivray, G.: The firefighter problem: a survey of results, directions and questions. Aust. J. Comb. 43, 57-77 (2009) · Zbl 1179.05112 |
| [11] | Goel, A., Rai, S., Krishnamachari, B.: Sharp thresholds for monotone properties in random geometric graphs. Ann. Appl. Probab. 15, 364-370 (2005) · Zbl 1098.60011 · doi:10.1214/105051605000000575 |
| [12] | Janson, S., Łuczak, T., Ruciński, A.: Random Graphs. Wiley, New York (2000) · Zbl 0968.05003 · doi:10.1002/9781118032718 |
| [13] | Kehagias, A., Mitsche, D., Prałat, P.: Cops and invisible robbers: the cost of drunkenness. Theor. Comput. Sci. 481, 100-120 (2013) · Zbl 1291.91039 · doi:10.1016/j.tcs.2013.01.032 |
| [14] | Kehagias, A., Prałat, P.: Some remarks on cops and drunk robbers. Theor. Comput. Sci. 463, 133-147 (2012) · Zbl 1258.91042 · doi:10.1016/j.tcs.2012.08.016 |
| [15] | Land, M., Lu, L.: An upper bound on burning number of graphs. arXiv:1606.07614 · Zbl 1398.68405 |
| [16] | Penrose, M.: The longest edge of the random minimal spanning tree. Ann. Appl. Probab. 7(2), 340-361 (1997) · Zbl 0884.60042 · doi:10.1214/aoap/1034625335 |
| [17] | Penrose, M.: Random Geometric Graphs. Oxford Studies in Probability, Oxford U.P., Oxford (2003) · Zbl 1029.60007 · doi:10.1093/acprof:oso/9780198506263.001.0001 |
| [18] | Prałat, P.: Cleaning random \[d\] d-regular graphs with Brooms. Gr. Comb. 27, 567-584 (2011) · Zbl 1235.05126 · doi:10.1007/s00373-010-0986-x |
| [19] | Prałat, P.: Cleaning random graphs with brushes. Aust. J. Comb. 43, 237-251 (2009) · Zbl 1155.05336 |
| [20] | Prałat, P.: Graphs with average degree smaller than 30/11 burn slowly. Gr. Comb. 30(2), 455-470 (2014) · Zbl 1298.05225 · doi:10.1007/s00373-012-1265-9 |
| [21] | Prałat, P.: Sparse graphs are not flammable. SIAM J. Discrete Math. 27(4), 2157-2166 (2013) · Zbl 1285.05124 · doi:10.1137/120876113 |
| [22] | Roshanbin, E.: Burning a graph as a model of social contagion. PhD Thesis, Dalhousie University (2016) · Zbl 1342.05154 |
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.
