首页 | 本学科首页   官方微博 | 高级检索  
     检索      


A lower bound of the surviving rate of a planar graph with girth at least seven
Authors:Weifan Wang  Stephen Finbow  Ping Wang
Institution:1. Department of Mathematics, Zhejiang Normal University, Jinhua, 321004, China
2. Department of Mathematics, Statistics and Computer Science, St. Francis Xavier University, Antigonish, Nova Scotia, Canada
Abstract:Let G be a connected graph with n≥2 vertices. Suppose that a fire breaks out at a vertex v of G. A firefighter starts to protect vertices. At each time interval, the firefighter protects one vertex not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbor on fire. Let sn(v) denote the maximum number of vertices in G that the firefighter can save when a fire breaks out at vertex v. The surviving rate ρ(G) of G is defined to be ∑ vV(G)sn(v)/n 2, which is the average proportion of saved vertices. In this paper, we show that if G is a planar graph with n≥2 vertices and having girth at least 7, then $\rho(G)>\frac{1}{301}$ .
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号