Meyniel's conjecture holds for random graphs |
| |
| Authors: | Pawe? Pra?at Nicholas Wormald |
| |
| Affiliation: | 1. Department of Mathematics, Ryerson University, Toronto, Ontario, Canada;2. School of Mathematical Sciences, Monash University, Victoria, Australia |
| |
| 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  . In this paper, we show that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph  , which improves upon existing results showing that asymptotically almost surely the cop number of  is  provided that  for some  . 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  . © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 396–421, 2016 |
| |
| Keywords: | random graphs vertex‐pursuit games Cops and Robbers expansion properties |
|
|
