Characterization of k-cop-win graphs

Joel Faubert

Introduction to the game of Cops and Robbers on Graphs. Definition of the cop-number of a graph c(G): the minimum number of cops required to guarantee the robber is caught. Characterization of k-cop win graphs by the existence of a function satisfying certain properties. Pseudo-code and running time of polynomial algorithm for decision problem ``Is G k-cop Win for fixed k?''