不含短圈的平面图的存活率  

The Surviving Rate of Planar Graphs without Short Cycles

作　　者：王维凡[1] 胡嘉程 WANG WEIFAN;HU JIACHENG(Department of Mathematics,Zhejiang Normal University,Jinhua 321004,China)

机构地区：[1]浙江师范大学数学系,金华321004

出　　处：《应用数学学报》2023年第4期493-506,共14页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金(12031018,11771402,12226303)资助项目。

摘　　要：设G是一个n-阶连通图(n≥2).假设火在G的某点v处燃起,消防员选择一个未着火的顶点进行保护,然后火蔓延到v的未被保护且没有着火的邻点.当火在点v处燃起时,消防员最多能保护到的顶点数记为sn(v).定义v∈V(G)∑sn(v)/n^(2)为G的存活率.容易看到0 <ρ(G)<1.本文证明了:若平面图G不含长度从4到11的圈,则ρ(G)>1/481.Let G be a connected graph with n≥2 vertices.Suppose that a fire breaks out at a vertex of G,a firefighter starts to protects the vertices of G by choosing a vertex not yet fire.Then the fire spreads to all the unprotected vertices that have a neighbor on fre.Let sn(u)denote the maximum number of vertices in G that the firefighter can save when a fire breaks out at vertex v.The surviving rate p(G)of G is defined to be v∈V(G)∑sn(v)/n^(2).It is easy to see that 0<p(G)<1.In this paper we show that if G is a planar graph withoutall cycles of length from 4 to 1,hen p(G)>1/481.

关 键 词：消防员问题 存活率 平面图 圈 

分 类 号：O157.5[理学—数学]