|
|
Pure Mathematics 2025
图的两类燃烧问题研究
|
Abstract:
图的燃烧理论涉及无向图和有向图，燃烧数刻画了无向图的抗毁性。燃烧连通度将燃烧数和连通度结合，刻画出有向图抗毁的能力，基于此，通过研究证明出
阶定向完全图的燃烧连通度的界，并在燃烧数和燃烧连通度的基础上，引入充分燃烧数的定义，用于衡量有向图充分燃烧的过程，以及刻画有向图燃烧后产生的结果。并根据此定义，计算出星图、双星图以及完全二部图
的充分燃烧数。
The burning theory of graphs involves undirected graphs and directed graphs. The burning number characterizes the invulnerability of undirected graphs. The burning connectivity combines the burning number and the connectivity, depicting the invulnerability of directed graphs. Based on this, research has proven the bounds of the burning connectivity of n-order directed complete graphs. Moreover, on the basis of the burning number and the burning connectivity, the definition of the sufficient burning number is introduced, which is used to measure the process of sufficient burning of directed graphs and to characterize the results generated after the directed graphs are burned. According to this definition, the sufficient burning numbers of star graphs, double-star graphs, and complete bipartite graphs
are calculated.
| [1] | Finbow, S., King, A., MacGillivray, G. and Rizzi, R. (2007) The Firefighter Problem for Graphs of Maximum Degree Three. Discrete Mathematics, 307, 2094-2105. https://doi.org/10.1016/j.disc.2005.12.053 |
| [2] | Simon, M., Huraj, L., Dirgova Luptakova, I. and Pospichal, J. (2019) How to Burn a Network or Spread Alarm. MENDEL, 25, 11-18. https://doi.org/10.13164/mendel.2019.2.011 |
| [3] | 王维凡, 孔将旭. 图的存活率与消防员问题[J]. 数学进展, 2021, 50(1): 1-21. |
| [4] | Bonato, A., Janssen, J. and Roshanbin, E. (2016) How to Burn a Graph. Internet Mathematics, 12, 85-100. https://doi.org/10.1080/15427951.2015.1103339 |
| [5] | Bessy, S., Bonato, A., Janssen, J., Rautenbach, D. and Roshanbin, E. (2017) Burning a Graph Is Hard. Discrete Applied Mathematics, 232, 73-87. https://doi.org/10.1016/j.dam.2017.07.016 |
| [6] | Das, S., Dev, S.R., Sadhukhan, A., et al. (2018) Burning Spiders. In: Panda, B. and Goswami, P., Eds., Algorithms and Discrete Applied Mathematics, Springer, 155-163. https://doi.org/10.1007/978-3-319-74180-2_13 |
| [7] | Bonato, A. and Lidbetter, T. (2019) Bounds on the Burning Numbers of Spiders and Path-forests. Theoretical Computer Science, 794, 12-19. https://doi.org/10.1016/j.tcs.2018.05.035 |
| [8] | Liu, H., Hu, X. and Hu, X. (2020) Burning Number of Caterpillars. Discrete Applied Mathematics, 284, 332-340. https://doi.org/10.1016/j.dam.2020.03.062 |
| [9] | Janssen, R. (2020) The Burning Number of Directed Graphs: Bounds and Computational Complexity. arXiv: 2001.03381. |
| [10] | 夏龙苗, 魏宗田, 丁丽萍. 定向图的燃烧连通度[J]. 山东大学学报(理学版), 2023, 58(12): 127-133. |
| [11] | 薛睿滢, 魏宗田, 翟美娟. 图的限制性燃烧连通度[J]. 山东大学学报(理学版), 2024, 59(2): 91-99, 109. |
| [12] | 卓新建, 苏永美, 编著. 图论及其应用[M]. 北京: 北京邮电大学出版社, 2018. |
| [13] | Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. Springer. https://doi.org/10.1007/978-1-84628-970-5 |
