Name
Abstract | ||
|---|---|---|
Let [email protected]? be a connected digraph with n>=2 vertices. Suppose that a fire breaks out at a vertex v of [email protected]?. 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 sn"k(v) denote the maximum number of vertices in [email protected]? that the firefighter can save when a fire breaks out at vertex v. The k-surviving rate @r"k([email protected]?) of [email protected]? is defined as @?"v"@?"V"("G"@?")sn"k(v)/n^2. In this paper, we consider the k-surviving rate of digraphs. Main results are as follows: (1) if [email protected]? is a k-degenerate digraph, then @r"k([email protected]?)>=1k+1; (2) if [email protected]? is a planar digraph, then @r"2([email protected]?)>140; (3) if [email protected]? is a planar digraph without 4-cycles, then @r"1([email protected]?)>151. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.disc.2014.06.018 | Discrete Mathematics |
Keywords | Field | DocType |
firefighter problem,surviving rate,planar graph,discharging,digraph | Discrete mathematics,Combinatorics,Vertex (geometry),Planar graph,Digraph,Mathematics | Journal |
Volume | Issue | ISSN |
334 | 1 | 0012-365X |
Citations | PageRank | References |
6 | 0.57 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jiangxu Kong | 1 | 32 | 3.41 |
| Lian-Zhu Zhang | 2 | 33 | 9.04 |
| Weifan Wang | 3 | 868 | 89.92 |