NIC-平面图的存活率

作者：孔将旭; 郭文婷; 胡晓雪; 王维凡^*

来源：应用数学学报, 2023, 46(01): 21-31.

• NIC-平面图
• 存活率
• 消防员问题

假设火在图G的某个顶点燃起,消防员每步最多可以防护k个顶点,然后火蔓延到所有未被防护的邻点.当火随机地在图G的一个顶点燃起时,消防员最多能防护的顶点数的平均比率称为图G的k-存活率,记为ρk(G).如果图G能画在平面上使得每两对交叉边至多有一个公共顶点,那么称G是NIC-平面图.本文证明了NIC-平面图G有ρ5(G)> 1/73.

• 单位
  浙江科技学院; 中国计量大学; 浙江师范大学