Zombie outbreak on a $k$-regular graph Suppose we have a zombie outbreak on a connected $k$-regular graph of order $n$.  There are $n_0$ initially infected zombie nodes, and each turn, each zombie infects its neighbors with probability $p$.  Let $z(t)$ denote the number of infected nodes on turn $t$.


*

*What is the expected number of turns until zombies have taken over the world?  (that is, until $z(t)=n$?)

*Is it true that $z(t)\approx \dfrac{n}{1+(n-n_0)e^{-rt}}$?  If so, what is $r$?
 A: Once $k>2$ the answer to #1 depends on the graph;
even in the limiting determinstic case of $p=1$, and taking $n_0=1$,
the expected time till full zombification can range from about $C \log n$
(for an expander graph) to at least $n/k$ (when $k$ is even, the node set is
${\bf Z}/n{\bf Z}$, and each node is joined to its $k$ nearest neighbors).
As to #2: for large $t$, the probability that there is still an
uninfected node $-$ which is essentially the difference between $n$
and the expected value of $z(t)$ $-$ decays exponentially with $t$.
The base of the exponent is $(1-p)^{b_{\min}}$, where $b_{\min}$ 
is the minimum number $b(S)$ of edges connecting $S$ and its complement,
and $S$ ranges over all nonempty sets of nodes that are initially uninfected
and might become the set of yet-uninfected nodes at some point.
(This assumes of course that $n_0<n$: if $n_0=n$ then $z(t)=n$
for all $n$.)  Usually $b=k$, realized by singleton sets;
but $b$ can be smaller if the graph has a bottleneck,
e.g. for this cubic graph

(source: harvard.edu) 
the base is $1-p$ as long as the zombies were initially on
just one side of the graph.
To obtain the $(1-p)^{b_{\min}}$ formula, 
regard the outbreak as a dynamical system on the
subsets $S$ of the set $S_0$ of initially uninfected nodes.
At each $t$ the system's state is the set of nodes
not yet infected by time $t$.
The probability that $S$ goes to itself is $(1-p)^{b(S)}$,
and otherwise $S$ goes to a proper subset.  Thus the
dynamical system is triangular (with respect to the
partial order of set inclusion), with eigenvalues equal to 
the diagonal entries $(1-p)^{b(S)}$.
The dominant eigenvalue of $1$ occurs only for $S=\emptyset$
because the graph is connected.  The next eigenvalue is 
$(1-p)^{b_{\min}}$, and occurs for all nonempty $S$ minimizing $b(S)$;
these are usually but not always the singletons in $S_0$.
(Sometimes not every $S \subset S_0$ can be reached from $S_0$, but clearly
at one singleton is reachable unless $n_0=n$.)
