Paper Info
Title
Meyniel's conjecture holds for random d-regular graphs
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 sqrt{|V(G)|}$. In a separate paper, we showed that Meynielu0027s 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) ge 3$.
Year
Venue
Field
2019
Random Struct. Algorithms
Random regular graph,Discrete mathematics,Graph,Combinatorics,Random graph,Vertex (geometry),Binomial,Almost surely,Connectivity,Conjecture,Mathematics
DocType
Citations 
PageRank 
Journal
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Pawel Pralat123448.16
Nick Wormald241.81