Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418662 | Discrete Applied Mathematics | 2015 | 6 Pages |
Abstract
We study 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∞(G)c∞(G) denote the number of cops needed to capture the robber in graph GG in this variant. We show that if GG is an interval graph, then c∞(G)∈O(|V(G)|); while for every nn there exists an nn-vertex chordal graph GG with c∞(G)∈Ω(n/logn)c∞(G)∈Ω(n/logn). This indicates a large contrast between interval graphs and chordal graphs in this variant, whereas in the original Cops and Robber game a single cop suffices for both classes.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Abbas Mehrabian,