Seminar: Graphs with average degree smaller than 30/11 burn slowly

Speaker: Pawel Pralat, TMU

Title: Graphs with average degree smaller than 30/11 burn slowly

Abstract: I did not find any speaker for this week so I will tell you about some very old project that probably nobody heard about. 

Consider the following \emph{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 one vertex which is 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 $\varepsilon >0$. We show that any graph $G$ on $n$ vertices with at most $(\frac {15}{11}-\varepsilon)n$ edges can be well protected, that is, $\rho(G) > \frac {\varepsilon}{60} > 0$. Moreover, a construction of a random graph is proposed to show that the constant $\frac {15}{11}$ cannot be improved.