On a generalization of Meyniel's conjecture on the cops and Robbers game

Noga Alon, Abbas Mehrabian

Research output: Contribution to journalArticle

12 Scopus citations

Abstract

We consider a variant of the Cops and Robbers game where the robber can move s edges at a time, and show that in this variant, the cop number of a connected graph on n vertices can be as large as Ω(ns/s+1) This improves the Ω(ns-3/s-2) lower bound of Frieze et al. [5], and extends the result of the second author [10], which establishes the above bound for s = 2, 4.

Original languageEnglish (US)
Pages (from-to)1-7
Number of pages7
JournalElectronic Journal of Combinatorics
Volume18
Issue number1
DOIs
StatePublished - Jan 1 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'On a generalization of Meyniel's conjecture on the cops and Robbers game'. Together they form a unique fingerprint.

  • Cite this