Search

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 two vertices not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let sn"2(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 @r"2(G) of G is defined to be @?"v"@?"V"("G")sn"2(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 without 4-cycles, then @r"2(G)>176.

Let G be a connected graph with n>=2 vertices. Let k>=1 be an integer. 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 k-vertices 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"k(v) denote the maximum number of vertices in G that the firefighter can save when a fire breaks out at vertex v. The k-surviving rate @r"k(G) of G is defined to be @?"v"@?"V"("G")sn"k(v)/n^2, which is the average proportion of saved vertices. In this paper, we show that every planar graph G with minimum degree @d satisfies @r"4(G)>311 if @d=5, @r"4(G)>319 if @d=4, and @r"4(G)>19 if @d@?3. This improves a result in [W. Wang, S. Finbow, P. Wang, The surviving rate of an infected network, Theoret. Comput. Sci. 411 (2010) 3651-3660].

Let G be a connected graph with n>=2 vertices. Let k>=1 be an integer. 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 k-vertices not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let sn"k(v) denote the maximum number of vertices in G that the firefighter can save when a fire breaks out at vertex v. The k-surviving rate @r"k(G) of G is defined to be @?"v"@?"V"("G")sn"k(v)/n^2, which is the average proportion of saved vertices. In this paper, we investigate the surviving rate of outerplanar graphs G with n>=2 vertices. The main results are as follows: (1) lim"n"->"[email protected]"5(G)=1; and (2) @r"1(G)>=4381-53n+3n^2 if n>=8, and @r"1(G)>=13 if n>=2, which improves the result in [L.Cai, W.Wang, The surviving rate of a graph for the firefighter problem, SIAM J. Discrete Math. 23 (2009) 1814-1826].

Let G be a connected network. Let k>=1 be an integer. Suppose that a vertex v of G becomes infected. A program is then installed on k-nodes not yet infected. Afterwards, the virus spreads to all its unprotected neighbors in each time interval. The virus and the network administrator take turns until the virus can no longer spread further. Let sn"k(v) denote the maximum number of vertices in G the network administrator can save when a virus infects v. The k-surviving rate @r"k(G) of G is defined to be the average value @?"v"@?"V"("G")sn"k(v)/n^2. In particular, we write @r(G)[email protected]"1(G). In this paper, we first use a probabilistic method to show that almost all networks have k-surviving rate arbitrarily close to 0. Then, we prove the following results: (1) @r(G)>=235 for a planar network G of girth at least 9; (2) @r"2(G)>=116 for a series-parallel network G; and (3) @r"""2"""d"""-"""1(G)>=25d for a d-degenerate network G.