On the problem of burning and protecting of weighted graphs

Journal of Lanzhou University of Technology ›› 2025, Vol. 51 ›› Issue (2): 152-158.

• Scientific • Previous Articles Next Articles

On the problem of burning and protecting of weighted graphs

LI Ruo-tong, WEI Zong-tian

School of Science, Xi’an University of Architecture and Technology, Xi’an 710055, China

Received:2023-05-17 Online:2025-04-28 Published:2025-04-29

Abstract

Abstract: In order to reduce the loss caused by network disruptions, it is necessary to consider the protection strategy. Combining the idea of the firefighter problem with graph burning, the concepts of the relative protection strategy and maximum protection rate of weighted graphs are proposed. The maximum protecting rate calculation formulas of several types of typically weighted graphs and the constructing method of extremely weighted graphs based on the maximum protecting rate are given. Additionally, an approximation algorithm is designed for computing the maximum protection rate of general trees with radius 2 and 3. The relationships between the maximum protection rate, the weight values, the way of weighting, and the structure of graphs are revealed.

Key words: weighted graph, graph burning, protection strategy, maximum protecting rate, weighting

CLC Number:

O157.5

LI Ruo-tong, WEI Zong-tian. On the problem of burning and protecting of weighted graphs[J]. Journal of Lanzhou University of Technology, 2025, 51(2): 152-158.

References

[1] 王维凡,孔将旭.图的存活率与消防员问题 [J].数学进展,2021,50(1):1-21.
[2] HARTNELL B.Firefighter! an application of domination [R].Winnipeg:University of Manitoba,1995.
[3] 翁婷婷,魏宗田.图的赋权邻域坚韧度 [J].山东大学学报(理学版),2022,57(6):36-43.
[4] 邢之尧.统计模型中若干格子图的消防员问题 [D].新疆:新疆师范大学,2022.
[5] 郭文婷,孔将旭.不含5-圈平面图的边存活率 [J].中国计量大学学报,2020,31(4):519-523.
[6] 刘佩佩,何志红.图的广义燃烧数及其界值问题 [J].烟台大学学报(自然科学与工程版),2022,35(4):385-389.
[7] 刘佩佩,何志红.图的积的广义燃烧数 [J].赤峰学院学报(自然科学版),2022,38(1):1-4.
[8] 郭文婷.图的燃烧数和存活率研究 [D].杭州:中国计量大学,2021.
[9] 卢鹏丽,周庚.基于邻介熵和邻度熵的复杂网络中心性算法 [J].兰州理工大学学报,2021,47(4):91-98.
[10] CAI L Z,WANG W F.The surviving rate of a graph for the firefighter problem [J].SIAM Journal on Discrete Mathematics,2009,23(4):1814-1826.
[11] BONDY J A,MURTY U S R.Graph theory [M].London:Springer,2008.
[12] BONATO A,JANSSEN J,ROSHANBIN E.How to burn a graph [J].Internet Mathematics,2016,12(1/2):85-100.
[13] 魏宗田,刘勇,杨威,等.网络抗毁性 [M].西安:西安交通大学出版社,2015.
[14] BONDY J A,MURTY U S R.Graph theory with applications [M].London:Macmillan,1976.
[15] 张胜贵,李学良,王力工.通信系统抗破坏能力研究 [J].西北工业大学学报,2002,20(1):100-103.
[16] COZZENS M,WU S.Edge-neighbor-integrity of trees [J].Australasian Journal of Combinatorics,1994,10(10):163-174.
[17] 杨雪.图的广义p-邻域抗毁性参数研究 [D].西安:西安建筑科技大学,2021.
[18] 杨胜良,姜美杨.混合d-元树上的模式避免问题 [J].兰州理工大学学报,2023,49(2):144-150.

On the problem of burning and protecting of weighted graphs

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

Comments

[1]	LI Meng-xuan, WEI Zong-tian. Weighted edge neighbor toughness of graphs [J]. Journal of Lanzhou University of Technology, 2025, 51(1): 158-165.
[2]	GUO Run-lan, DENG Wen-qiang, LI Dian-lun. Optimization design and performance analysis of CNC machine tools composite structure bed based on grey theory [J]. Journal of Lanzhou University of Technology, 2021, 47(5): 53-58.