Chasing a fast robber on planar graphs and random graphs

Noga Alon, Abbas Mehrabian

Research output: Contribution to journalArticle

9 Scopus citations

Abstract

We consider a variant of the Cops and Robber game, in which the robber has unbounded speed, that is, can take any path from her vertex in her turn, but she is not allowed to pass through a vertex occupied by a cop. Let c(G) denote the number of cops needed to capture the robber in a graph G in this variant, and let tw(G) denote the tree-width of G. We show that if G is planar then c(G) = Θ(tw(G)), and there is a polynomial-time constant-factor approximation algorithm for computing c∞(G).We also determine, up to constant factors, the value of c(G) of the Erdo″s-Rényi random graph G = G(n, p) for all admissible values of p, and show that when the average degree is ω(1), c(G) is typically asymptotic to the domination number.

Original languageEnglish (US)
Pages (from-to)81-96
Number of pages16
JournalJournal of Graph Theory
Volume78
Issue number2
DOIs
StatePublished - Jan 1 2015

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • Cops and robber game
  • Domination number
  • Fast robber
  • Planar graphs
  • Random graphs
  • Treewidth

Fingerprint Dive into the research topics of 'Chasing a fast robber on planar graphs and random graphs'. Together they form a unique fingerprint.

  • Cite this