Extremal cop-win graphs:(Fridays at 11:45 am at CUNY GC (365 Fifth Avenue) Room 4419)
The game of cops and robber is a two player game, played on a graph, between a cop and a robber. First the cop chooses a vertex, then the robber chooses a vertex; then play alternates. On a turn, a player may move to an adjacent vertex or remain still. A graph is cop-win if the cop can guarantee a win. For a cop-win graph, the capture time is the number of moves required by one cop to catch the robber. We consider graphs that are extremal (or almost extremal) with respect to capture time, i.e. their capture time is as large as possible relative to their order. We reprove an old result characterizing such extremal graphs (our proof avoids the use of a computer search) and prove a new result, characterizing almost extremal graphs. Our new approach involves associating graphs to vectors (i.e. finite lists of integers) and then partially determining which vectors can be realized by some graph. We leave fully characterizing these vectors as an open question. This is joint work with David Offner.
More details are available on the seminar webpage: