Name
Abstract | ||
|---|---|---|
Let $$G$$G be a connected graph with $$n\\ge 2$$n¿2 vertices. Let $$k\\ge 1$$k¿1 be an integer. Suppose that a fire breaks out at a vertex $$v$$v of $$G$$G. A firefighter starts to protect vertices. At each step, the firefighter protects $$k$$k-vertices not yet on fire. At the end of each step, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let $$\\hbox {sn}_k(v)$$snk(v) denote the maximum number of vertices in $$G$$G that the firefighter can save when a fire breaks out at vertex $$v$$v. The $$k$$k-surviving rate $$\\rho _k(G)$$¿k(G) of $$G$$G is defined to be $$\\frac{1}{n^2}\\sum _{v\\in V(G)} {\\hbox {sn}}_{k}(v)$$1n2¿v¿V(G)snk(v), which is the average proportion of saved vertices. In this paper, we prove that if $$G$$G is a planar graph with $$n\\ge 2$$n¿2 vertices and without 5-cycles, then $$\\rho _2(G)\\frac{1}{363}$$¿2(G)1363. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/s10878-015-9835-4 | J. Comb. Optim. |
Keywords | DocType | Volume |
Firefighter problem,Surviving rate,Cycle,Planar graph | Journal | 31 |
Issue | ISSN | Citations |
4 | 1382-6905 | 4 |
PageRank | References | Authors |
0.43 | 14 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tingting Wu | 1 | 32 | 4.45 |
| Jiangxu Kong | 2 | 32 | 3.41 |
| Weifan Wang | 3 | 868 | 89.92 |