Back to Search
Start Over
The surviving rate of digraphs.
- Source :
-
Discrete Mathematics . Nov2014, Vol. 334, p13-19. 7p. - Publication Year :
- 2014
-
Abstract
- Let ... be a connected digraph with n≥2 vertices. Suppose that a fire breaks out at a vertex v of .... A firefighter starts to protect vertices. At each time interval, the firefighter protects k vertices not yet on fire. Afterward, the fire spreads to all unprotected neighbors that are heads of some arcs starting from the vertices on fire. Let snk(v) denote the maximum number of vertices in ... that the firefighter can save when a fire breaks out at vertex v. The k-surviving rate ρk(...) of ... is defined as .... In this paper, we consider the k-surviving rate of digraphs. Main results are as follows: (1) if ... is a k-degenerate digraph, then ρk(...)≥1/k+1; (2) if ... is a planar digraph, then ρ2(...)>1/40; (3) if ... is a planar digraph without 4-cycles, then ρ1(...)>1/51. [ABSTRACT FROM AUTHOR]
- Subjects :
- *DIRECTED graphs
*GRAPH theory
*NUMBER theory
*PLANAR graphs
*MATHEMATICAL analysis
Subjects
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 334
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 97419429
- Full Text :
- https://doi.org/10.1016/j.disc.2014.06.018