Meyniel's conjecture holds for random graphs

Pawel Pralat, Nicholas Wormald

Research output: Contribution to journalArticleResearchpeer-review

5 Citations (Scopus)

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(nlogn) provided that pn≥(2+ε)logn 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.

Original languageEnglish
Pages (from-to)396-421
Number of pages26
JournalRandom Structures & Algorithms
Volume48
Issue number2
DOIs
Publication statusPublished - 1 Mar 2016

Keywords

  • Cops and Robbers
  • Expansion properties
  • Random graphs
  • Vertex-pursuit games

Cite this