  We prove new theoretical results about several variations of the cop and
robber game on graphs. First, we consider a variation of the cop and robber
game which is more symmetric called the cop and killer game. We prove for all
$c < 1$ that almost all random graphs are stalemate for the cop and killer
game, where each edge occurs with probability $p$ such that $\frac{1}{n^{c}}
\le p \le 1-\frac{1}{n^{c}}$. We prove that a graph can be killer-win if and
only if it has exactly $k\ge 3$ triangles or none at all. We prove that graphs
with multiple cycles longer than triangles permit cop-win and killer-win
graphs. For $\left(m,n\right)\neq\left(1,5\right)$ and $n\geq4$, we show that
there are cop-win and killer-win graphs with $m$ $C_n$s. In addition, we
identify game outcomes on specific graph products.
  Next, we find a generalized version of Dijkstra's algorithm that can be
applied to find the minimal expected capture time and the minimal evasion
probability for the cop and gambler game and other variations of graph pursuit.
  Finally, we consider a randomized version of the killer that is similar to
the gambler. We use the generalization of Dijkstra's algorithm to find optimal
strategies for pursuing the random killer. We prove that if $G$ is a connected
graph with maximum degree $d$, then the cop can win with probability at least
$\frac{\sqrt d}{1+\sqrt d}$ after learning the killer's distribution. In
addition, we prove that this bound is tight only on the
$\left(d+1\right)$-vertex star, where the killer takes the center with
probability $\frac1{1+\sqrt d}$ and each of the other vertices with equal
probabilities.
