Projects per year
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 CV(G). In this paper, we show that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph G(n,p), which improves upon existing results showing that asymptotically almost surely the cop number of G(n,p) is O(nlogn) provided that pn≥(2+ε)logn for some ε>0. We do this by first showing that the conjecture holds for a general class of graphs with some specific expansiontype properties. This will also be used in a separate paper on random dregular graphs, where we show that the conjecture holds asymptotically almost surely when d=d(n)≥3.
Original language  English 

Pages (fromto)  396421 
Number of pages  26 
Journal  Random Structures and Algorithms 
Volume  48 
Issue number  2 
DOIs  
Publication status  Published  1 Mar 2016 
Keywords
 Cops and Robbers
 Expansion properties
 Random graphs
 Vertexpursuit games
Projects
 1 Finished

Advances in the analysis of random structures and their applications: relationships among models
Australian Research Council (ARC)
1/08/12 → 31/12/17
Project: Research