Meyniel's conjecture holds for random d-regular graphs

Paweł Prałat, Nicholas Wormald

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (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 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.

Original languageEnglish
Pages (from-to)719-741
Number of pages23
JournalRandom Structures & Algorithms
Volume55
Issue number3
DOIs
Publication statusPublished - 1 Jan 2019

Keywords

  • cops and robbers
  • random graphs
  • vertex-pursuit games

Cite this