ABSTRACT
This chapter focuses on first and arguably most famous graph searching game, Cops and Robbers. It analyzes Cops and Robbers on random structures, or uses the probabilistic method to derive properties in the deterministic case. The chapter presents some background on Cops and Robbers, and examines the cop number of dense random graphs. In Cops and Robbers, a two-player game of perfect information, a set of cops tries to capture a robber by moving at unit speed from vertex to vertex. If a cop is placed at each vertex, then the cops are guaranteed to win. The chapter discusses random graphs with constant cop number, and proves that almost all cop-win graphs have a universal vertex by showing that almost all k-cop-win graphs have a dominating set of order k. It also analyzes Cops and Robbers games in random geometric graphs and percolated random geometric graphs, respectively.
