1. The surviving rate of an outerplanar graph for the firefighter problem
- Author
-
Wang, Weifan, Yue, Xubin, and Zhu, Xuding
- Subjects
- *
GRAPH theory , *FIRE fighters , *VERTEX operator algebras , *COMPUTER science , *ALGORITHMS , *INTEGER programming - Abstract
Abstract: Let be a connected graph with vertices. Let be an integer. Suppose that a fire breaks out at a vertex of . A firefighter starts to protect vertices. At each time interval, the firefighter protects -vertices not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let sn denote the maximum number of vertices in that the firefighter can save when a fire breaks out at vertex . The -surviving rate of is defined to be , which is the average proportion of saved vertices. In this paper, we investigate the surviving rate of outerplanar graphs with vertices. The main results are as follows: (1) ; and (2) if , and if , which improves the result in [L.Cai, W.Wang, The surviving rate of a graph for the firefighter problem, SIAM J. Discrete Math. 23 (2009) 1814–1826]. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF