Planar graphs without chordal 5-cycles are 2-good
Planar graphs without chordal 5-cycles are 2-good
复制标题
没有弦 5 圈的平面图是 2 好图
DOI：
10.1007/s10878-017-0243-9
复制
发表时间：
2018
影响因子：
1
通讯作者：
Yiqiao Wang
中科院分区：
文献类型：
--
作者：
Weifan Wang;Tingting Wu;Xiaoxue Hu;Yiqiao Wang
让G成为一个有顶点的连通图。假设在 G 的顶点 v 处发生火灾。消防员开始保护顶点。在每一步中，消防员都会保护两个尚未着火的顶点。在每个步骤结束时，火势都会蔓延到所有有邻居着火的未受保护的顶点。让sn表示当顶点v发生火灾时消防员可以拯救的最大顶点数。 Gi的2-存活率被定义为实数。那么很明显。如果存在这样的常数，则该图称为 2-good。在本文中，我们证明每个有顶点且没有弦 5 圈的平面图都是 2-good。
LetGbe a connected graph withvertices. Suppose that a fire breaks out at a vertexvofG. A firefighter starts to protect vertices. At each step, the firefighter protects two vertices not yet on fire. At the end of each step, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let sndenote the maximum number of vertices inGthat the firefighter can save when a fire breaks out at vertexv. The 2-surviving rateofGis defined to be the real number. Then it is obvious that. The graphGis called 2-good if there is a constantsuch that. In this paper, we prove that every planar graph withvertices and without chordal 5-cycles is 2-good.