Meyniel's conjecture holds for random d‐regular graphs. Issue 3 (7th July 2019)

• Record Type: Journal Article
• Authors: Prałat, Paweł; Wormald, Nicholas
• Is Part Of: Random structures & algorithms. Volume 55:Issue 3(2019)
• Page Start: 719
• Page End: 741
• Publication Date: 2019-07-07
• Subjects: cops and robbers -- random graphs -- vertex‐pursuit games; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20874
• 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 a separate paper, we showed that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph. The result was obtained by showing that the conjecture holds for a general class of graphs with some specific expansion‐type properties. In this paper, this deterministic result is used to show that the conjecture holds asymptotically almost surely for random d ‐regular graphs when d = d ( n ) ≥ 3.