Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T14:08:08.317Z Has data issue: false hasContentIssue false
  • English
  • Français

Lower Bounds for the Cop Number when the Robber is Fast

Published online by Cambridge University Press:  19 April 2011

ABBAS MEHRABIAN
ABBAS MEHRABIAN*
Affiliation:
Department of Combinatorics and Optimization, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, CanadaN2L 3G1 (e-mail: amehrabian@uwaterloo.ca)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 Ω(dt). 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 Ω(n2/3) if t ≥ 2, and Ω(n4/5) if t ≥ 4. This improves the Ω($n^{\frac{t-3}{t-2}}$) lower bound of Frieze, Krivelevich and Loh (Variations on cops and robbers, J. Graph Theory, to appear) when 2 ≤ t ≤ 6. We also conjecture a general upper bound O(nt/t+1) for the cop number in this variant, generalizing Meyniel's conjecture.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 4 , July 2011 , pp. 617 - 621
Copyright
Copyright © Cambridge University Press 2011

References

[1]Alon, N. and Mehrabian, A. (2011) On a generalization of Meyniel's conjecture on the Cops and Robbers game. Electron. J. Combin. 18 #19.CrossRefGoogle Scholar
[2]Araujo, G., González, D., Montellano-Ballesteros, J. J. and Serra, O. (2007) On upper bounds and connectivity of cages. Austral. J. Combin. 38 221–228.Google Scholar
[3]Exoo, G. and Jajcay, R. (2008) Dynamic cage survey. Electron. J. Combin. 15 #16.Google Scholar
[4]Fomin, F. V., Golovach, P. A., Kratochvíl, J., Nisse, N. and Suchan, K. (2010) Pursuing a fast robber on a graph. Theoret. Comput. Sci. 411 1167–1181.CrossRefGoogle Scholar
[5]Frankl, P. (1987) Cops and robbers in graphs with large girth and Cayley graphs. Discrete Appl. Math. 17 301–305.CrossRefGoogle Scholar
[6]Frieze, A., Krivelevich, M. and Loh, P. (2011) Variations on cops and robbers. J. Graph Theory, to appear.CrossRefGoogle Scholar
[7]Hahn, G. (2007) Cops, robbers and graphs. Tatra Mt. Math. Publ. 36 163–176.Google Scholar
[8]Lazebnik, F., Ustimenko, V. A. and Woldar, A. J. (1997) New upper bounds on the order of cages. Electron. J. Combin. 4 #13.Google Scholar
[9]Lu, L. and Peng, X. On Meyniel's conjecture of the cop number. Submitted.Google Scholar
[10]Nowakowski, R. and Winkler, P. (1983) Vertex-to-vertex pursuit in a graph. Discrete Math. 43 235–239.CrossRefGoogle Scholar
[11]Quilliot, A. (1978) Jeux et pointes fixes sur les graphes. PhD thesis, Université de Paris VI.Google Scholar
[12]Scott, A. and Sudakov, B. A new bound for the cops and robbers problem. arXiv:1004.2010v1 [math.CO].Google Scholar