We consider Containment: a variation of the graph pursuit game of Cops and Robber in which cops move from edge to adjacent edge, the robber moves from vertex to adjacent vertex (but cannot move along an edge occupied by a cop), and the cops win by containing the robber---that is, by occupying all $deg(v)$ of the edges incident with a vertex $v$ while the robber is at $v$. We develop bounds that relate the minimal number of cops, $xi(G)$, required to contain a robber to the well-known cop-number $c(G)$ in the original game: in particular, $c(G) {le} xi(G) {le} gamma(G) Delta(G)$. We note that $xi(G) {geq} delta(G)$ for all graphs $G$, and analyze several families of graphs in which equality holds, as well as several in which the inequality is strict. We also give examples of graphs which require an unbounded number of cops in order to contain a robber, and note that there exist cubic graphs with $xi(G) geq Omega(n^{1/6})$.
تحميل البحث