NIC-平面图的存活率

The Surviving Rate of NIC-Planar Graphs

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

Suppose that a fire starts at some vertex of a graph G.At every step,a firefighter can protect at most k vertices,and then the fire spreads to all unprotected neighbors.The k-surviving rate ρk(G) of G is the expectation of the proportion of vertices that can be saved from the fire,if the starting vertex of the fire is chosen uniformly at random.A graph is NIC-planar if it can be drawn in the plane such that each pairs of crossing edges share at most one vertex.In this paper,we prove that every NIC-planar graph G satisfies ρ5(G)>1/73.