A lower bound of the surviving rate of a planar graph with girth at least seven

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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial optimization 2014-05, Vol.27 (4), p.621-642
Main Authors: Wang, Weifan, Finbow, Stephen, Wang, Ping
Format: Article
Language:English
Subjects:
Combinatorics
Convex and Discrete Geometry
Mathematical Modeling and Industrial Mathematics
Mathematics
Mathematics and Statistics
Operations Research/Decision Theory
Optimization
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ∑ v ∈ V ( 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 .
ISSN:1382-6905
1573-2886
DOI:10.1007/s10878-012-9541-4