{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,10]],"date-time":"2024-04-10T02:13:57Z","timestamp":1712715237128},"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":"We consider a variant of the Cops and Robbers game where the robber can movet<\/jats:italic>edges at a time, and show that in this variant, the cop number of ad<\/jats:italic>-regular graph with girth larger than 2t<\/jats:italic>+2 is \u03a9(d<\/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 connectedn<\/jats:italic>-vertex graph can be as large as \u03a9(n<\/jats:italic>2\/3<\/jats:sup>) ift<\/jats:italic>\u2265 2, and \u03a9(n<\/jats:italic>4\/5<\/jats:sup>) ift<\/jats:italic>\u2265 4. This improves the \u03a9($n^{\\frac{t-3}{t-2}}$<\/jats:alt-text><\/jats:inline-graphic>) lower bound of Frieze, Krivelevich and Loh (Variations on cops and robbers,J. Graph Theory<\/jats:italic>, to appear) when 2 \u2264t<\/jats:italic>\u2264 6. We also conjecture a general upper boundO<\/jats:italic>(n<\/jats:italic>t<\/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":[]}],"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]]}}}