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

来源：应用数学学报杂志2023年第4期北京时间：

作者：王维凡, 胡嘉程

单位：浙江师范大学数学系, 金华 321004

摘要：设$G$是一个$n$-阶连通图($n\geq 2$).假设火在$G$的某点$v$处燃起,消防员选择一个未着火的顶点进行保护,然后火蔓延到$v$的未被保护且没有着火的邻点.当火在点$v$处燃起时,消防员最多能保护到的顶点数记为sn$(v)$.定义$\rho (G):=\sum\limits_{v\in V (G)}\frac{{\rm sn}(v)}{n^2}$为$G$的存活率.容易看到$0<\rho (G)<1$.本文证明了:若平面图$G$不含长度从4到11的圈,则$\rho (G)>\frac{1}{481}$.

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