Cops and Robber Game with a Fast Robber on Expander Graphs and Random Graphs

摘要

We consider a variant of the Cops and Robber game, in which the robber has unbounded speed, i.e., can take any path from her vertex in her turn, but she is not allowed to pass through a vertex occupied by a cop. Let ${c_{infty}(G)}$ denote the number of cops needed to capture the robber in a graph G in this variant. We characterize graphs G with c ∞(G) = 1, and give an ${O( mid V(G)mid^2)}$ algorithm for their detection. We prove a lower bound for c ∞ of expander graphs, and use it to prove three things. The first is that if ${np geq 4.2 {rm log}n}$ then the random graph ${G= mathcal{G}(n, p)}$ asymptotically almost surely has ${eta_{1}/p leq eta_{2}{rm log}(np)/p}$ , for suitable positive constants ${eta_{1}}$ and ${eta_{2}}$ . The second is that a fixed-degree random regular graph G with n vertices asymptotically almost surely has ${c_{infty}(G) = Theta(n)}$ . The third is that if G is a Cartesian product of m paths, then ${n/4km^2 leq c_{infty}(G) leq n/k}$ , where ${n = mid V(G)mid}$ and k is the number of vertices of the longest path.