The fast robber on interval and chordal graphs

摘要

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(infinity)(G) denote the number of cops needed to capture the robber in graph G in this variant. We show that if G is an interval graph, then c(infinity)(G) is an element of 0(root vertical bar V(G)vertical bar); while for every n there exists an n-vertex chordal graph G with c(infinity)(G) is an element of Omega(n/log n). 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. (C) 2014 Elsevier B.V. All rights reserved.