Name
Abstract | ||
|---|---|---|
For Hartnell's firefighter game with f vertices initially on fire and at most d defended vertices per round, the surviving rate ¿ ( G , f , d ) of a graph G is the average proportion of its vertices that can be saved in the game on G , where the average is taken over all sets of f fire sources. Cai et al. (2010) showed that ¿ ( T , 1 , 1 ) = 1 - O ( log n n ) = 1 - o ( 1 ) for every tree T of order n .We study the maximum value c ( f , d ) such that ¿ ( T , f , d ) ¿ c ( f , d ) - o ( 1 ) for every tree T of order n , where the o ( 1 ) term tends to 0 as n tends to infinity. In this notation, the result of Cai et al. states c ( 1 , 1 ) = 1 . Our main results are that c ( f , 1 ) ¿ ( 1 3 ) f and that 4 9 ¿ c ( 2 , 1 ) ¿ 3 4 . |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.dam.2014.10.031 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Firefighter game,Surviving rate | Discrete mathematics,Graph,Binary logarithm,Combinatorics,Vertex (geometry),Infinity,Mathematics | Journal |
Volume | Issue | ISSN |
184 | C | 0166-218X |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vitor Costa | 1 | 27 | 4.27 |
| Simone Dantas | 2 | 119 | 24.99 |
| Dieter Rautenbach | 3 | 946 | 138.87 |