Planar graphs without chordal 5-cycles are 2-good

被引:4
作者
Wang, Weifan [1 ]
Wu, Tingting [1 ]
Hu, Xiaoxue [1 ]
Wang, Yiqiao [2 ]
机构
[1] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Peoples R China
[2] Beijing Univ Chinese Med, Sch Management, Beijing 100029, Peoples R China
关键词
Firefighter problem; Surviving rate; Planar graph; Cycle; Chord; FIREFIGHTER PROBLEM; 2-SURVIVING RATE; SURVIVING RATE; FIRE;
D O I
10.1007/s10878-017-0243-9
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
Let G be a connected graph with vertices. Suppose that a fire breaks out at a vertex v of G. 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 sn denote the maximum number of vertices in G that the firefighter can save when a fire breaks out at vertex v. The 2-surviving rate of G is defined to be the real number . Then it is obvious that . The graph G is called 2-good if there is a constant such that . In this paper, we prove that every planar graph with vertices and without chordal 5-cycles is 2-good.
引用
收藏
页码:980 / 996
页数:17
相关论文
共 21 条
[1]   The firefighter problem with more than one firefighter on trees [J].
Bazgan, Cristina ;
Chopin, Morgan ;
Ries, Bernard .
DISCRETE APPLIED MATHEMATICS, 2013, 161 (7-8) :899-908
[2]   SURVIVING RATES OF GRAPHS WITH BOUNDED TREEWIDTH FOR THE FIREFIGHTER PROBLEM [J].
Cai, Leizhen ;
Cheng, Yongxi ;
Verbin, Elad ;
Zhou, Yuan .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (04) :1322-1335
[3]   THE SURVIVING RATE OF A GRAPH FOR THE FIREFIGHTER PROBLEM [J].
Cai Leizhen ;
Wang Weifan .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (04) :1814-1826
[4]   Fire Containment in Planar Graphs [J].
Esperet, Louis ;
van den Heuvel, Jan ;
Maffray, Frederic ;
Sipma, Felix .
JOURNAL OF GRAPH THEORY, 2013, 73 (03) :267-279
[5]   The firefighter problem for graphs of maximum degree three [J].
Finbow, Stephen ;
King, Andrew ;
MacGillivray, Gary ;
Rizzi, Romeo .
DISCRETE MATHEMATICS, 2007, 307 (16) :2094-2105
[6]  
Finbow S, 2009, AUSTRALAS J COMB, V43, P57
[7]   Planar graph is on fire [J].
Gordinowicz, Przemyslaw .
THEORETICAL COMPUTER SCIENCE, 2015, 593 :160-164
[8]  
Jin J, 2017, DISCRET MATH ALGORIT, V9, DOI 10.1142/S1793830917500112
[9]  
Karst N, 2017, DISCRET MATH ALGORIT, V9, DOI 10.1142/S1793830917500318
[10]   The firefighter problem for cubic graphs [J].
King, Andrew ;
MacGillivray, Gary .
DISCRETE MATHEMATICS, 2010, 310 (03) :614-621