id: 06099123
dt: j
an: 06099123
au: Seager, Suzanne
ti: Locating a robber on a graph.
so: Discrete Math. 312, No. 22, 3265-3269 (2012).
py: 2012
pu: Elsevier Science B.V. (North-Holland), Amsterdam
la: EN
cc: 
ut: graph game; robber; locating
ci: 
li: doi:10.1016/j.disc.2012.07.029
ab: Summary: Consider the following game of a cop locating a robber on a
    connected graph. At each turn, the cop chooses a vertex of the graph to
    probe and receives the distance from the probe to the robber. If she
    can uniquely locate the robber after this probe, then she wins.
    Otherwise the robber may either stay put or move to any vertex adjacent
    to his location other than the probe vertex. The cop’s goal is to
    minimize the number of probes required to locate the robber, while the
    robber’s goal is to avoid being located. This is a synthesis of the
    cop and robber game with the metric dimension problem. We analyse this
    game for several classes of graphs, including cycles and trees.
rv: