图的两类燃烧问题研究
Research on Two Types of Burning Problems of Graphs
DOI: 10.12677/pm.2025.157205, PDF,    科研立项经费支持
作者: 方德伟, 李 鹏, 赵天放：重庆理工大学数学科学学院，重庆
关键词: 定向图；燃烧数；燃烧连通度；充分燃烧数；Directed Graph； Burning Number； Burning Connectivity； Full Burning Number
摘要: 图的燃烧理论涉及无向图和有向图，燃烧数刻画了无向图的抗毁性。燃烧连通度将燃烧数和连通度结合，刻画出有向图抗毁的能力，基于此，通过研究证明出 n 阶定向完全图的燃烧连通度的界，并在燃烧数和燃烧连通度的基础上，引入充分燃烧数的定义，用于衡量有向图充分燃烧的过程，以及刻画有向图燃烧后产生的结果。并根据此定义，计算出星图、双星图以及完全二部图 K 2,n 的充分燃烧数。
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 K 2,n are calculated.
文章引用：方德伟, 李鹏, 赵天放. 图的两类燃烧问题研究[J]. 理论数学, 2025, 15(7): 45-52. https://doi.org/10.12677/pm.2025.157205

参考文献

[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. [Google Scholar] [CrossRef] 
[2] Simon, M., Huraj, L., Dirgova Luptakova, I. and Pospichal, J. (2019) How to Burn a Network or Spread Alarm. MENDEL, 25, 11-18. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[5] Bessy, S., Bonato, A., Janssen, J., Rautenbach, D. and Roshanbin, E. (2017) Burning a Graph Is Hard. Discrete Applied Mathematics, 232, 73-87. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[7] Bonato, A. and Lidbetter, T. (2019) Bounds on the Burning Numbers of Spiders and Path-forests. Theoretical Computer Science, 794, 12-19. [Google Scholar] [CrossRef] 
[8] Liu, H., Hu, X. and Hu, X. (2020) Burning Number of Caterpillars. Discrete Applied Mathematics, 284, 332-340. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 

为你推荐