Planar graphs without chordal 5-cycles are 2-good |
| |
Authors: | Weifan Wang Tingting Wu Xiaoxue Hu Yiqiao Wang |
| |
Institution: | 1.Department of Mathematics,Zhejiang Normal University,Jinhua,China;2.School of Management,Beijing University of Chinese Medicine,Beijing,China |
| |
Abstract: | Let G be a connected graph with \(n\ge 2\) 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\(_2(v)\) 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 \(\rho _2(G)\) of G is defined to be the real number \(\frac{1}{n^2} \sum _{v\in V(G)} \mathrm{sn}_2(v)\). Then it is obvious that \(0<\rho _2(G)<1\). The graph G is called 2-good if there is a constant \(c>0\) such that \(\rho _2(G)>c\). In this paper, we prove that every planar graph with \(n\ge 2\) vertices and without chordal 5-cycles is 2-good. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|