Meyniel's conjecture holds for random graphs1. Issue 2 (31st March 2015)

• Record Type: Journal Article
• Authors: Prałat, Paweł; Wormald, Nicholas
• Is Part Of: Random structures & algorithms. Volume 48:Issue 2(2016)
• Page Start: 396
• Page End: 421
• Publication Date: 2015-03-31
• Subjects: random graphs -- vertex‐pursuit games -- Cops and Robbers -- expansion properties; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20587
• Languages: English
• ISSNs: 1042-9832

Abstract

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 | V ( 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 ( n log n ) provided that p n ≥ ( 2 + ε ) log n for some ε > 0 . 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 ) ≥ 3 . © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 396–421, 2016