Lower bounds for the cop number when the robber is fast

DOI10.1017/S0963548311000101MaRDI QIDQ5199510zbMATH OpenOpenAlexFDO

Authors Abbas Mehrabian

Publication date 16 August 2011

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1007.1734

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Games involving graphs (91A43)

Abstract: We consider a variant of the Cops and Robbers game where the robber can move t edges at a time, and show that in this variant, the cop number of a d-regular graph with girth larger than 2t+2 is Omega(d^t). By the known upper bounds on the order of cages, this implies that the cop number of a connected n-vertex graph can be as large as Omega(n^{2/3}) if t>1, and Omega(n^{4/5}) if t>3. This improves the Omega(n^{(t-3)/(t-2)}) lower bound of Frieze, Krivelevich, and Loh (Variations on Cops and Robbers, J. Graph Theory, 2011) when 1<t<7. We also conjecture a general upper bound O(n^{t/t+1}) for the cop number in this variant, generalizing Meyniel's conjecture.

Recommendations

• On a generalization of Meyniel's conjecture on the Cops and Robbers game
• Variations on cops and robbers
• A bound for the cops and robbers problem
• Cops and Robber game with a fast robber on expander graphs and random graphs
• Catching an infinitely fast robber on a grid

Cites work

• Cops and robbers in graphs with large girth and Cayley graphs
• Pursuing a fast robber on a graph
• Vertex-to-vertex pursuit in a graph

Cited in

(8)

• 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
• Variations on cops and robbers
• The fast robber on interval and chordal graphs
• On the cop number of graphs of high girth
• On a generalization of Meyniel's conjecture on the Cops and Robbers game

This page was built for publication: Lower bounds for the cop number when the robber is fast

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