Premium
Meyniel's conjecture holds for random d ‐regular graphs
Author(s) -
Prałat Paweł,
Wormald Nicholas
Publication year - 2019
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.20874
Subject(s) - mathematics , conjecture , combinatorics , discrete mathematics , graph , random regular graph , random 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 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.