基于多火源燃烧连通度的网络抗毁性分析

Analysis of network invulnerability based on the multi-fire source burning connectivity

摘要

给出几类笛卡尔积图的多火源燃烧连通度,分析多火源燃烧连通度与图结构的关系,提出多火源燃烧连通度的反问题:给定正数 m,确定火源,使得最多在 m 步内将图燃烧为不连通或空集,且所含顶点数尽可能地少(最小火源)。最后,给出一个求图的最小火源的算法。

Abstract

The multi-fire source burning connectivity is given for several types of Cartesian product graphs. The relationship between multi-fire source burning connectivity and graph structure is analyzed, and the inverse problem of multi-fire source burning connectivity is proposed, that is, given a positive number m, determine the fire source such that the graph is burned as disconnected or empty within m steps at most, and contains as few vertices as possible (the minimum fire source). Finally, an algorithm of the minimum fire source of graphs is designed.

关键词

图 / 抗毁性 / 多火源燃烧连通度 / 笛卡尔积图 / 算法

Key words

graph / invulnerability / multi-fire source burning connectivity / Cartesian product graphs / algorithm

参考文献

[1] 魏宗田, 刘勇, 杨威, 等. 网络抗毁性[M]. 西安:西安交通大学出版社, 2015: 34-35.

[2] WEI Zongtian, LIU Yong, YANG Wei, et al. Network invulnerability[M]. Xi'an: Xi'an Jiaotong University Press, 2015: 34-35.

[3] BONATO A, JANSSEN J, ROSHANBIN E. How to burn a graph[J]. Internet Mathematics, 2016, 12(1/2): 85-100.

[4] 白月蓉, 魏宗田. 图的多火源燃烧连通度[J]. 纯粹数学与应用数学, 2026, 42(1): 78-85.

[5] BAI Yuerong, WEI Zongtian. Multi—fire source burning connectivity of graphs[J]. Pure and Applied Mathematics, 2026, 42(1): 78-85.

[6] 徐俊明. 图论及其应用[M]. 4版. 合肥:中国科学技术大学出版社, 2018.

[7] XU Junming. Theory and applications of graphs[M]. 4th ed. Hefei: University of Science and Technology of China Press, 2018.

[8] BONDY J A, MURTY U S R. Graph theory[M]. London: Springer, 2008.

[9] 梅银珍, 符惠芬. 四类运算图的Sombor指数[J]. 山东大学学报(理学版), 2024, 59(6): 56-63.

[10] MEI Yinzhen, FU Huifeng. Sombor index on four operation graphs[J]. Journal of Shandong University(Natural Science), 2024, 59(6): 56-63.

[11] 薛睿滢, 魏宗田, 翟美娟. 图的限制性燃烧连通度[J]. 山东大学学报(理学版), 2024, 59(2): 91-99.

[12] XUE Ruiying, WEI Zongtian, ZHAI Meijuan. Restricted burning connectivity of graphs[J]. Journal of Shandong University(Natural Science), 2024, 59(2): 91-99.

基金资助

陕西数理基础科学研究项目(22JSQ029)