不含5-圈平面图的边存活率

The edge surviving rate of planar graphs without 5-cycles

目的:主要研究最小度至少为3且不含5-圈的连通平面图的(4,2)-边存活率。方法:主要利用平面图分离定理和图染色理论中的经典方法权转移进行推导证明。结果:得到了如果G是最小度至少为3的不含5-圈的连通平面图,那么图G的(4,2)-边存活率至少为1/62。结论:当火随机的在最小度至少为3且不含5-圈的连通平面图G的两个相邻顶点燃起时,消防员采取第一步保护4个点,后面每一步保护2个点的防火策略,使得最后获救的顶点数的平均值至少为图G顶点数的1/62。

Aims:This paper aims to study the(4,2)-edge surviving rate of a connected planar graph without 5-cycles and with minimum degrees of at least 3.Methods:Using the planar separator theorem and discharging method,which was a classical method in the graph theory,results were deduced and proved.Results:It was found that if G was a connected planar graph without 5-cycles and with minimum degrees of at least 3,then the(4,2)-edge surviving rate of G was at least 1/62.Conclusions:The expected percentage of vertices that can be saved by the firefighter is at least 1/62 with the strategy that protects 4 vertices at the first step and 2 vertices at subsequent steps,when fires randomly break out at two adjacent vertices of a connected planar graph without 5-cycles and with minimum degrees of at least 3.