The 2-surviving rate of planar graphs without 5-cycles |
| |
Authors: | Tingting?Wu Jiangxu?Kong Email author" target="_blank">Weifan?WangEmail author |
| |
Institution: | 1.Department of Mathematics,Zhejiang Normal University,Jinhua,China;2.School of Mathematical Science,Xiamen University,Fujian,China |
| |
Abstract: | Let \(G\) be a connected graph with \(n\ge 2\) vertices. Let \(k\ge 1\) be an integer. Suppose that a fire breaks out at a vertex \(v\) of \(G\). A firefighter starts to protect vertices. At each step, the firefighter protects \(k\)-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 \(\hbox {sn}_k(v)\) denote the maximum number of vertices in \(G\) that the firefighter can save when a fire breaks out at vertex \(v\). The \(k\)-surviving rate \(\rho _k(G)\) of \(G\) is defined to be \(\frac{1}{n^2}\sum _{v\in V(G)} {\hbox {sn}}_{k}(v)\), which is the average proportion of saved vertices. In this paper, we prove that if \(G\) is a planar graph with \(n\ge 2\) vertices and without 5-cycles, then \(\rho _2(G)>\frac{1}{363}\). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|