{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:16:24Z","timestamp":1787501784338,"version":"build-2736575974"},"reference-count":12,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2011,4,19]],"date-time":"2011-04-19T00:00:00Z","timestamp":1303171200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2011,7]]},"abstract":"<jats:p>\n                    We consider a variant of the Cops and Robbers game where the robber can move\n                    <jats:italic>t<\/jats:italic>\n                    edges at a time, and show that in this variant, the cop number of a\n                    <jats:italic>d<\/jats:italic>\n                    -regular graph with girth larger than 2\n                    <jats:italic>t<\/jats:italic>\n                    +2 is \u03a9(\n                    <jats:italic>d<\/jats:italic>\n                    <jats:sup>\n                      <jats:italic>t<\/jats:italic>\n                    <\/jats:sup>\n                    ). By the known upper bounds on the order of cages, this implies that the cop number of a connected\n                    <jats:italic>n<\/jats:italic>\n                    -vertex graph can be as large as \u03a9(\n                    <jats:italic>n<\/jats:italic>\n                    <jats:sup>2\/3<\/jats:sup>\n                    ) if\n                    <jats:italic>t<\/jats:italic>\n                    \u2265 2, and \u03a9(\n                    <jats:italic>n<\/jats:italic>\n                    <jats:sup>4\/5<\/jats:sup>\n                    ) if\n                    <jats:italic>t<\/jats:italic>\n                    \u2265 4. This improves the \u03a9(\n                    <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548311000101_inline1\">\n                      <jats:alt-text>$n^{\\frac{t-3}{t-2}}$<\/jats:alt-text>\n                    <\/jats:inline-graphic>\n                    ) lower bound of Frieze, Krivelevich and Loh (Variations on cops and robbers,\n                    <jats:italic>J. Graph Theory<\/jats:italic>\n                    , to appear) when 2 \u2264\n                    <jats:italic>t<\/jats:italic>\n                    \u2264 6. We also conjecture a general upper bound\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    <jats:sup>\n                      <jats:italic>t<\/jats:italic>\n                      \/\n                      <jats:italic>t<\/jats:italic>\n                      +1\n                    <\/jats:sup>\n                    ) for the cop number in this variant, generalizing Meyniel's conjecture.\n                  <\/jats:p>","DOI":"10.1017\/s0963548311000101","type":"journal-article","created":{"date-parts":[[2011,4,19]],"date-time":"2011-04-19T06:43:31Z","timestamp":1303195411000},"page":"617-621","source":"Crossref","is-referenced-by-count":6,"title":["Lower Bounds for the Cop Number when the Robber is Fast"],"prefix":"10.1017","volume":"20","author":[{"given":"ABBAS","family":"MEHRABIAN","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2011,4,19]]},"reference":[{"key":"S0963548311000101_ref1","doi-asserted-by":"crossref","DOI":"10.37236\/506","article-title":"On a generalization of Meyniel's conjecture on the Cops and Robbers game","volume":"18","author":"Alon","year":"2011","journal-title":"Electron. J. Combin."},{"key":"S0963548311000101_ref2","first-page":"221","article-title":"On upper bounds and connectivity of cages","volume":"38","author":"Araujo","year":"2007","journal-title":"Austral. J. Combin."},{"key":"S0963548311000101_ref7","first-page":"163","article-title":"Cops, robbers and graphs","volume":"36","author":"Hahn","year":"2007","journal-title":"Tatra Mt. Math. Publ."},{"key":"S0963548311000101_ref6","doi-asserted-by":"crossref","unstructured":"[6] Frieze A. , Krivelevich M. and Loh P. (2011) Variations on cops and robbers. J. Graph Theory, to appear.","DOI":"10.1002\/jgt.20591"},{"key":"S0963548311000101_ref9","unstructured":"[9] Lu L. and Peng X. On Meyniel's conjecture of the cop number. Submitted."},{"key":"S0963548311000101_ref11","unstructured":"[11] Quilliot A. (1978) Jeux et pointes fixes sur les graphes. PhD thesis, Universit\u00e9 de Paris VI."},{"key":"S0963548311000101_ref8","article-title":"New upper bounds on the order of cages","volume":"4","author":"Lazebnik","year":"1997","journal-title":"Electron. J. Combin."},{"key":"S0963548311000101_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90160-7"},{"key":"S0963548311000101_ref3","article-title":"Dynamic cage survey","volume":"15","author":"Exoo","year":"2008","journal-title":"Electron. J. Combin."},{"key":"S0963548311000101_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.12.010"},{"key":"S0963548311000101_ref12","unstructured":"[12] Scott A. and Sudakov B. A new bound for the cops and robbers problem. arXiv:1004.2010v1 [math.CO]."},{"key":"S0963548311000101_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90033-3"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548311000101","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,18]],"date-time":"2020-06-18T07:03:33Z","timestamp":1592463813000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548311000101\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,4,19]]},"references-count":12,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["S0963548311000101"],"URL":"https:\/\/doi.org\/10.1017\/s0963548311000101","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,4,19]]}}}