The burning number $ b(G) $ of a graph $ G $, introduced by Bonato, is the minimum number of steps to burn the graph, which is a model for the spread of influence in social networks. In 2016, Bonato et al. studied the burning number of paths and cycles, and based on these results, they proposed a conjecture on the upper bound for the burning number. In this paper, we determine the exact value of the burning number of $ Q $ graphs and confirm this conjecture for $ Q $ graph. Following this, we characterize the single tail and double tails $ Q $ graph in term of their burning number, respectively.
Citation: Yinkui Li, Jiaqing Wu, Xiaoxiao Qin, Liqun Wei. Characterization of $ Q $ graph by the burning number[J]. AIMS Mathematics, 2024, 9(2): 4281-4293. doi: 10.3934/math.2024211
The burning number $ b(G) $ of a graph $ G $, introduced by Bonato, is the minimum number of steps to burn the graph, which is a model for the spread of influence in social networks. In 2016, Bonato et al. studied the burning number of paths and cycles, and based on these results, they proposed a conjecture on the upper bound for the burning number. In this paper, we determine the exact value of the burning number of $ Q $ graphs and confirm this conjecture for $ Q $ graph. Following this, we characterize the single tail and double tails $ Q $ graph in term of their burning number, respectively.
| [1] |
J. A. Bondy, U. S. R. Murty, Graph theory with applications, J. Oper. Res. Soc., 28 (1977), 237–238. http://dx.doi.org/10.1057/jors.1977.45 doi: 10.1057/jors.1977.45
|
| [2] | A. Bonato, J. Janssen, E. Roshanbin, Burning a graph as a model of social contagion, In: Algorithms and models for the web graph, 2014. https://doi.org/10.1007/978-3-319-13123-8_2 |
| [3] |
A. Bonato, J. Janssen, E. Roshanbin, How to burn a graph, Internet Math., 12 (2016), 85–100. http://dx.doi.org/10.1080/15427951.2015.1103339 doi: 10.1080/15427951.2015.1103339
|
| [4] |
A. Bonato, J. Janssen, E. Roshanbin, Burning a graph is hard, Discrete Appl. Math., 232 (2017), 73–87. http://dx.doi.org/10.1016/j.dam.2017.07.016 doi: 10.1016/j.dam.2017.07.016
|
| [5] |
N. Alon, P. Pralat, N. Wormald, Cleaning regular graphs with brushes, Siam. J. Discrete Math., 23 (2008), 233–250. http://dx.doi.org/10.1137/070703053 doi: 10.1137/070703053
|
| [6] |
A. Barghi, P. Winkler, Firefighting on a random geometric graph, Random. Struct. Algor., 46 (2015), 466–477. http://dx.doi.org/10.1002/rsa.20511 doi: 10.1002/rsa.20511
|
| [7] |
A. Bonato, T. Lidbetter, Bounds on the burning numbers of spiders and path-forests, Theor. Comput. Sci., 794 (2019), 12–19. http://dx.doi.org/10.1016/j.tcs.2018.05.035 doi: 10.1016/j.tcs.2018.05.035
|
| [8] |
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. http://dx.doi.org/10.1007/s40840-017-0585-6 doi: 10.1007/s40840-017-0585-6
|
| [9] |
D. Mitsche, P. Pralat, E. Roshanbin, Burning number of graph products, Theor. Comput. Sci., 746 (2018), 124–138. http://dx.doi.org/10.1016/j.tcs.2018.06.036 doi: 10.1016/j.tcs.2018.06.036
|
| [10] |
D. Mitsche, P. Pralat, E. Roshanbin, Burning graphs: A probabilistic perspective, Graph Combinator., 33 (2017), 449–471. http://dx.doi.org/10.1007/s00373-017-1768-5 doi: 10.1007/s00373-017-1768-5
|
| [11] |
H. Q. Liu, R. T. Zhang, X. L. Hu, Burning number of theta graphs, Appl. Math. Comput., 361 (2019), 246–257. http://dx.doi.org/10.1016/j.amc.2019.05.031 doi: 10.1016/j.amc.2019.05.031
|
| [12] |
H. Q. Liu, X. J. Hu, X. L. Hu, Burning numbers of path forests and spiders, Bull. Malays. Math. Sci. Soc., 44 (2021), 661–681. http://dx.doi.org/10.1007/s40840-020-00969-w doi: 10.1007/s40840-020-00969-w
|
Figures(1)
Yinkui Li, Jiaqing Wu, Xiaoxiao Qin, Liqun Wei. Characterization of $ Q $ graph by the burning number[J]. AIMS Mathematics, 2024, 9(2): 4281-4293. doi: 10.3934/math.2024211
DownLoad: