Premium
Meyniel's conjecture holds for random graphs
Author(s) -
Prałat Paweł,
Wormald Nicholas
Publication year - 2016
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20587
Subject(s) - conjecture , mathematics , combinatorics , graph , discrete mathematics , random graph , random regular graph , constant (computer programming) , chordal graph , 1 planar graph , computer science , programming language
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