Let $G = (V, E)$ be a connected, undirected graph. We begin by placing $a$ predators and $b$ prey on the graph: each one is placed at a node chosen uniformly at random. Each predator and each prey takes a random walk, traversing an edge (in sync) adjacent to its current position at times $t = 0, 1, 2, \dots$, independent of the predators and prey currently on the graph. If at time $t$ a vertex is occupied by a predator and at least one prey, all of the prey on this vertex are removed from the graph. Nothing happens if a predator and a prey pass on an edge.
Suppose that $G$ is not bipartite. Then I would like to compute the expected time (or at least a satisfactory upper bound for it) that all prey are eliminated for two cases: $(1)$: $a = b = 1$ and $(2)$: $a \geq 1$, $b \geq 1$. I exclude bipartite graphs because the expected time is infinite in such a case.
I think the first case can be treated if we construct another graph $G'$ which records all the possible positions of the predator and prey (i.e., each vertex in this graph would be an ordered pair of vertices in $V$). In terms of this new graph, the single prey is eliminated when a vertex of the form $(v,v)$ is occupied. Then it would just be a matter of computing the cover time of $G'$, for which a well known upper bound exists. Could we perhaps use this result to treat the second case?