{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,26]],"date-time":"2025-10-26T14:24:31Z","timestamp":1761488671068},"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>We consider a variant of the Cops and Robbers game where the robber can move<jats:italic>t<\/jats:italic>edges at a time, and show that in this variant, the cop number of a<jats:italic>d<\/jats:italic>-regular graph with girth larger than 2<jats:italic>t<\/jats:italic>+2 is \u03a9(<jats:italic>d<\/jats:italic><jats:sup><jats:italic>t<\/jats:italic><\/jats:sup>). By the known upper bounds on the order of cages, this implies that the cop number of a connected<jats:italic>n<\/jats:italic>-vertex graph can be as large as \u03a9(<jats:italic>n<\/jats:italic><jats:sup>2\/3<\/jats:sup>) if<jats:italic>t<\/jats:italic>\u2265 2, and \u03a9(<jats:italic>n<\/jats:italic><jats:sup>4\/5<\/jats:sup>) if<jats:italic>t<\/jats:italic>\u2265 4. This improves the \u03a9(<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548311000101_inline1\"><jats:alt-text>$n^{\\frac{t-3}{t-2}}$<\/jats:alt-text><\/jats:inline-graphic>) lower bound of Frieze, Krivelevich and Loh (Variations on cops and robbers,<jats:italic>J. Graph Theory<\/jats:italic>, to appear) when 2 \u2264<jats:italic>t<\/jats:italic>\u2264 6. We also conjecture a general upper bound<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup><jats:italic>t<\/jats:italic>\/<jats:italic>t<\/jats:italic>+1<\/jats:sup>) for the cop number in this variant, generalizing Meyniel's conjecture.<\/jats:p>","DOI":"10.1017\/s0963548311000101","type":"journal-article","created":{"date-parts":[[2011,4,19]],"date-time":"2011-04-19T10:43:31Z","timestamp":1303209811000},"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":[{"role":"author","vocabulary":"crossref"}]}],"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-18T11:03:33Z","timestamp":1592478213000},"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]]}}}