Bootstrap Percolation on Degenerate Graphs

In this paper we focus on $r$-neighbor bootstrap percolation, which is a process on a graph where initially a set $A_0$ of vertices gets infected. Now subsequently, an uninfected vertex becomes infected if it is adjacent to at least $r$ infected vertices. Call $A_f$ the set of vertices that is infected after the process stops. More formally set $A_t:=A_{t-1}\cup {v\in V: |N(v)\cap A_{t-1}|\geq r}$,where$N(v)$istheneighborhoodof$v$\mathrm{.}Then$A_f=\bigcup_{t>0} A_t$\mathrm{.}Wedealwithfinitegraphsonlyanddenoteby$n$ the number of vertices. We are mainly interested in the size of the final set $A_f$. We present a theorem for degenerate graphs that bounds the size of the final infected set. More precisely for a $d$-degenerate graph, if $r>d$, we bound the size set $A_f$ from above by $(1+\frac{d}{r-d})\mathrm{\mid }{A}_0\mathrm{\mid }$.