Sparse graphs are not flammable

Details Sparse graphs are not flammable Sparse graphs are not flammable

2012-01-03

arxiv.org/abs/1201.0723v1

Mathematics

Combinatorics

Scientific paper

In this paper, we consider the following \emph{$k$-many firefighter problem} on a finite graph $G=(V,E)$. Suppose that a fire breaks out at a given vertex $v \in V$. In each subsequent time unit, a firefighter protects $k$ vertices which are not yet on fire, and then the fire spreads to all unprotected neighbours of the vertices on fire. The objective of the firefighter is to save as many vertices as possible. The surviving rate $\rho(G)$ of $G$ is defined as the expected percentage of vertices that can be saved when a fire breaks out at a random vertex of $G$. Let $\tau_k = k+2-\frac {1}{k+2}$. We show that for any $\eps >0$ and $k \ge 2$, each graph $G$ on $n$ vertices with at most $(\tau_k-\eps)n$ edges is not flammable; that is, $\rho(G) > \frac {2\eps}{5\tau_k} > 0$. Moreover, a construction of a family of flammable random graphs is proposed to show that the constant $\tau_k$ cannot be improved.

Affiliated with

Also associated with

No associations

Rating

Sparse graphs are not flammable does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sparse graphs are not flammable, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sparse graphs are not flammable will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-184351