Meyniel's conjecture holds for random graphs

Abstract

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 the one of Meyniel, which asserts that for some absolute constant $C$, the cop number of every connected graph $G$ is at most $C\sqrt{|V(G)|}$. In this paper, we show that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph. We do this by first showing that the conjecture holds for a general class of graphs with some specific expansion-type properties. This will also be used in a separate paper on random $d$-regular graphs, where we show that the conjecture holds asymptotically almost surely when $d=d(n)\ge 3$.

revised version

Cited by in corpus (5)

• The robber strikes back
• Almost all k-cop-win graphs contain a dominating set of cardinality k
• Chasing robbers on random geometric graphs---an alternative approach
• Lazy Cops and Robbers played on Graphs
• Cops and Robbers on diameter two graphs