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

Noga Alon; Abbas Mehrabian

doi:10.37236/506

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

Noga Alon, Abbas Mehrabian

Research output: Contribution to journal › Article › peer-review

15 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 Ω(n^s/s+1) This improves the Ω(n^s-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 language	English (US)
Pages (from-to)	1-7
Number of pages	7
Journal	Electronic Journal of Combinatorics
Volume	18
Issue number	1
DOIs	https://doi.org/10.37236/506
State	Published - 2011
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Access to Document

10.37236/506

Cite this

@article{d2706d5d39f64b069f8e507dd20dbd4e,

title = "On a generalization of Meyniel's conjecture on the cops and Robbers game",

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.",

author = "Noga Alon and Abbas Mehrabian",

year = "2011",

doi = "10.37236/506",

language = "English (US)",

volume = "18",

pages = "1--7",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "1",

}

TY - JOUR

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

AU - Alon, Noga

AU - Mehrabian, Abbas

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=79551532761&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79551532761&partnerID=8YFLogxK

U2 - 10.37236/506

DO - 10.37236/506

M3 - Article

AN - SCOPUS:79551532761

SN - 1077-8926

VL - 18

SP - 1

EP - 7

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this