Recently, Bonato et al. (2024) introduced a new graph parameter, which is the cooling number of a graph $ G $, denoted as CL$ (G) $. In contrast with burning which seeks to minimize the number of rounds to burn all vertices in a graph, cooling seeks to maximize the number of rounds to cool all vertices in the graph. Cooling number is the compelling counterpart to the well-studied burning number, offering a new perspective on dynamic processes within graphs. In this paper, we showed that the cooling number of a classic cubic graph, the generalized Petersen graphs $ P(n, k) $, is $ \left\lfloor \frac{n}{2k} \right\rfloor + \left\lfloor \frac{k+1}{2} \right\rfloor +O(1) $ by the use of vertex-transitivity and combinatorial arguments. Particularly, we determined the exact values for CL$ (P(n, 1)) $ and CL$ (P(n, 2)) $.
Citation: Kai An Sim, Kok Bin Wong. On the cooling number of the generalized Petersen graphs[J]. AIMS Mathematics, 2024, 9(12): 36351-36370. doi: 10.3934/math.20241724
Recently, Bonato et al. (2024) introduced a new graph parameter, which is the cooling number of a graph $ G $, denoted as CL$ (G) $. In contrast with burning which seeks to minimize the number of rounds to burn all vertices in a graph, cooling seeks to maximize the number of rounds to cool all vertices in the graph. Cooling number is the compelling counterpart to the well-studied burning number, offering a new perspective on dynamic processes within graphs. In this paper, we showed that the cooling number of a classic cubic graph, the generalized Petersen graphs $ P(n, k) $, is $ \left\lfloor \frac{n}{2k} \right\rfloor + \left\lfloor \frac{k+1}{2} \right\rfloor +O(1) $ by the use of vertex-transitivity and combinatorial arguments. Particularly, we determined the exact values for CL$ (P(n, 1)) $ and CL$ (P(n, 2)) $.
| [1] |
S. Bessy, A. Bonato, J. Janssen, D. Rautenbach, E. Roshanbin, Burning a graph is hard, Discrete Appl. Math. 232 (2017), 73–87. https://doi.org/10.1016/j.dam.2017.07.016 doi: 10.1016/j.dam.2017.07.016
|
| [2] | A. Bonato, H. Milne, T. G. Marbach, T. Mishura, How to cool a graph, Toronto Metropolitan University, 2024. |
| [3] | A. Bonato, J. Janssen, E. Roshanbin, Burning a graph as a model of social contagion, In: Algorithms and models for the web graph, 8882 (2014), 13–22. https://doi.org/10.1007/978-3-319-13123-8_2 |
| [4] |
A. Bonato, J. Janssen, E. Roshanbin, How to burn a graph, Internet Math., 12 (2016), 85–100. https://doi.org/10.1080/15427951.2015.1103339 doi: 10.1080/15427951.2015.1103339
|
| [5] |
A. Bonato, 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 doi: 10.1016/j.tcs.2018.05.035
|
| [6] | S. Das, S. R. Dev, A. Sadhukhan, U. k. Sahoo, S. Sen, Burning spiders, In: Algorithms and discrete applied mathematics, 10743 (2018), 155–163. https://doi.org/10.1007/978-3-319-74180-2_13 |
| [7] | S. L. Fitzpatrick, L. Wilm, Burning circulant graphs, arXiv: 1706.03106, 2017. https://doi.org/10.48550/arXiv.1706.03106 |
| [8] | A. T. Gupta, S. A. Lokhande, K. Mondal, Burning grids and intervals, In: Algorithms and discrete applied mathematics, Cham: Springer, 12601 (2021), 66–79. https://doi.org/10.1007/978-3-030-67899-9_6 |
| [9] | M. Hiller, A. M. C. A. Koster, E. Triesch, On the burning number of p-caterpillars, In: Graphs and combinatorial optimization: From theory to applications, Cham: Springer, 2021,145–156. https://doi.org/10.1007/978-3-030-63072-0_12 |
| [10] | X. Hou, T. Wang, Wide diameters of generalized Petersen graphs, J. Math. Res. Exposition, 24 (2004), 249–253. |
| [11] | D. Knuth, The art of computer programming, Addison-Wesley, 1968. |
| [12] |
M. S. Krishnamoorthy, B. Krishnamurthy, Fault diameter of interconnection networks, Comput. Math. Appl., 13 (1987), 577–582. https://doi.org/10.1016/0898-1221(87)90085-X doi: 10.1016/0898-1221(87)90085-X
|
| [13] |
Y. Li, J. Wu, X. Qin, L. Wei, Characterization of $Q$ graph by the burning number, AIMS Mathematics, 9 (2024), 4281–4293. https://doi.org/10.3934/math.2024211 doi: 10.3934/math.2024211
|
| [14] |
H. Q. Liu, X. J. Hu, X. H. Hu, Burning number of caterpillars, Discrete Appl. Math., 284 (2020), 332–340. https://doi.org/10.1016/j.dam.2020.03.062 doi: 10.1016/j.dam.2020.03.062
|
| [15] |
H. Q. Liu, X. J. Hu, X. H. 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 doi: 10.1007/s40840-020-00969-w
|
| [16] |
H. Liu, R. Zhang, X. Hu, Burning number of theta graphs, Appl. Math. Comput., 361 (2019), 246–257. https://doi.org/10.1016/j.amc.2019.05.031 doi: 10.1016/j.amc.2019.05.031
|
| [17] | D. Mitsche, P. Prałat, E. Roshanbin, Burning graphs: A probabilistic perspective, Graphs Combin. 33 (2017), 449–471. https://doi.org/10.1007/s00373-017-1768-5 |
| [18] |
D. Mitsche, P. Prałat, E. Roshanbin, Burning number of graph products, Theoret. Comput. Sci., 746 (2018), 124–135. https://doi.org/10.1016/j.tcs.2018.06.036 doi: 10.1016/j.tcs.2018.06.036
|
| [19] |
K. A. Sim, T. S. Tan, 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 doi: 10.1007/s40840-017-0585-6
|
| [20] |
T. S. Tan, 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 doi: 10.1016/j.amc.2020.125447
|
| [21] |
T. S. Tan, 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 doi: 10.1016/j.amc.2022.127574
|
| [22] |
R. Zhang, Y. Yu, 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 doi: 10.1007/s40840-021-01194-9
|
Figures(3) / Tables(1)
Kai An Sim, Kok Bin Wong. On the cooling number of the generalized Petersen graphs[J]. AIMS Mathematics, 2024, 9(12): 36351-36370. doi: 10.3934/math.20241724
DownLoad: