This assignment studies the following variant of a cops-and-robber game on a graph G. Basically, in this version the robber moves along edges of the graph, one edge per game round; while the cops freely land on graph vertices, again one vertex per game round, and never move away from the vertices they have landed on. This game is with full information. Precisely, it is a turn-based game with the following steps:

1. The robber player chooses an initial vertex - his position, in the graph G.
2. The cop player (seeing robber's position) announces to the robber his next move - a vertex x to which a cop is going to land.
3. Then the robber player chooses to stay at its current vertex r, or to move to a neighbouring vertex of r (if any) not occupied by a cop.
4. The cop player occupies (lands on) the announced vertex x with a new cop. If the robber currently is at x, then the robber player looses the game. Otherwise, the game loops back to the point 2.

As you can see, the robber player is doomed to loose, but the question is in how many rounds (iterations of the above described game) he looses. With respect to this objective, we ask the following questions - to which (at least some of them) you have to find answers with mathematical proofs:

• (Mandatory warm-up which everybody must solve, but no points are given yet.) Determine the smallest number of rounds in which the cop player always wins the game when the graph is a path or a cycle of length n. Then prove that complete graphs are the only examples of simple graphs on n vertices such that the cop player needs n rounds to surely win.

• Find several (non-complete) graphs on n vertices on which the cop player needs at least n-1 rounds to surely win. Try to characterize all such graphs.
• Find examples of (infinite ones, or sequences of finite ones) trees on which the cop player needs an unbounded number of rounds to surely win. Try to find such tree examples that the number of required rounds is as large as possible compared to the number of all vertices.
• Explain on suitable examples of graphs that the character of the game dramatically changes when the robber is arbitrarily fast, i.e. if in step 3 the robber may move along an arbitrarily long cop-free path in each one round.

Deadline 30.11. 2011

Read the general remarks in parent section!