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

MaRDI QIDQ625381zbMATH OpenFDO

Authors Noga Alon, Abbas Mehrabian

Publication date 17 February 2011

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/231586, http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p19.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

Review text

Summary: 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 \(\Omega (n^{\frac{s}{s+1}})\). This improves the \(\Omega (n^{\frac{s-3}{s-2}})\) lower bound of Frieze et al. [\textit{A. Frieze}, \textit{M. Krivelevich}, and \textit{P. Loh}, ``Variations on cops and robbers, \url{arXiv:1004.2482}], and extends the result of the second author [\textit{A. Mehrabian}, ``Lower bounds for cop number when robber is fast, \url{arXiv:1007.1734}], which establishes the above bound for \(s = 2, 4\).

Recommendations

• Lower bounds for the cop number when the robber is fast
• Variations on cops and robbers
• A bound for the cops and robbers problem
• Meyniel's conjecture on the cop number: a survey
• Meyniel's conjecture on graphs of bounded degree

Cited in

(14)

• Spy-game on graphs: complexity and simple topologies
• A simple method for proving lower bounds in the zero-visibility cops and robber game
• Catching an infinitely fast robber on a grid
• Cops, a fast robber and defensive domination on interval graphs
• Catching a fast robber on the grid
• To satisfy impatient web surfers is hard
• Spy game: FPT-algorithm, hardness and graph products
• Spy game: FPT-algorithm and results on graph products
• Variations on cops and robbers
• Chasing a fast robber on planar graphs and random graphs
• A bound for the cops and robbers problem
• Lower bounds for the cop number when the robber is fast
• On the cop number of Sierpinski-like graphs
• Chasing robbers on random geometric graphs-an alternative approach

This page was built for publication: On a generalization of Meyniel's conjecture on the Cops and Robbers game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q625381)