Cops and robber on a random graph
|Affiliation:||University of Waterloo|
|Room:||Mathematics & Computer Building (MC) 5158|
In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. The biggest open conjecture in this area is Meyniel's, which asserts that for some absolute constant C, the cop number of every graph G is at most C|V(G)|. We show that Meyniel's conjecture holds asymptotically almost surely for G a random d-regular graph, d ≥ 3, as well as in the standard random graph model G(n,p).
200 University Avenue West
Waterloo, ON N2L 3G1