{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,6]],"date-time":"2026-02-06T04:50:28Z","timestamp":1770353428599,"version":"3.49.0"},"reference-count":34,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2012,8,16]],"date-time":"2012-08-16T00:00:00Z","timestamp":1345075200000},"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":[[2012,11]]},"abstract":"<jats:p>Cops and robbers is a turn-based pursuit game played on a graph <jats:italic>G<\/jats:italic>. One robber is pursued by a set of cops. In each round, these agents move between vertices along the edges of the graph. The cop number <jats:italic>c<\/jats:italic>(<jats:italic>G<\/jats:italic>) denotes the minimum number of cops required to catch the robber in finite time. We study the cop number of geometric graphs. For points <jats:italic>x<\/jats:italic><jats:sub>1<\/jats:sub>, .\u00a0.\u00a0., <jats:italic>x<jats:sub>n<\/jats:sub><\/jats:italic> \u2208 \u211d<jats:sup>2<\/jats:sup>, and <jats:italic>r<\/jats:italic> \u2208 \u211d<jats:sup>+<\/jats:sup>, the vertex set of the geometric graph <jats:italic>G(x<\/jats:italic><jats:sup>1<\/jats:sup>, .\u00a0.\u00a0., <jats:italic>x<jats:sub>n<\/jats:sub>; r<\/jats:italic>) is the graph on these <jats:italic>n<\/jats:italic> points, with <jats:italic>x<jats:sub>i<\/jats:sub>, x<jats:sub>j<\/jats:sub><\/jats:italic> adjacent when \u2225<jats:italic>x<jats:sub>i<\/jats:sub><\/jats:italic> \u2212 <jats:italic>x<jats:sub>j<\/jats:sub><\/jats:italic>\u2225 \u2264 <jats:italic>r<\/jats:italic>. We prove that <jats:italic>c<\/jats:italic>(<jats:italic>G<\/jats:italic>) \u2264 9 for any connected geometric graph <jats:italic>G<\/jats:italic> in \u211d<jats:sup>2<\/jats:sup> and we give an example of a connected geometric graph with <jats:italic>c<\/jats:italic>(<jats:italic>G<\/jats:italic>) = 3. We improve on our upper bound for random geometric graphs that are sufficiently dense. Let <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000338_char1\"\/><\/jats:private-char>(<jats:italic>n,r<\/jats:italic>) denote the probability space of geometric graphs with <jats:italic>n<\/jats:italic> vertices chosen uniformly and independently from [0,1]<jats:sup>2<\/jats:sup>. For <jats:italic>G<\/jats:italic> \u2208 <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000338_char1\"\/><\/jats:private-char>(<jats:italic>n,r<\/jats:italic>), we show that with high probability (w.h.p.), if <jats:italic>r<\/jats:italic> \u2265 <jats:italic>K<\/jats:italic><jats:sub>1<\/jats:sub> (log <jats:italic>n\/n<\/jats:italic>)<jats:sup>1\/4<\/jats:sup> then <jats:italic>c<\/jats:italic>(<jats:italic>G<\/jats:italic>) \u2264 2, and if <jats:italic>r<\/jats:italic> \u2265 <jats:italic>K<\/jats:italic><jats:sub>2<\/jats:sub>(log <jats:italic>n\/n<\/jats:italic>)<jats:sup>1\/5<\/jats:sup> then <jats:italic>c<\/jats:italic>(<jats:italic>G<\/jats:italic>) = 1, where <jats:italic>K<\/jats:italic><jats:sub>1<\/jats:sub>, <jats:italic>K<\/jats:italic><jats:sub>2<\/jats:sub> &gt; 0 are absolute constants. Finally, we provide a lower bound near the connectivity regime of <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000338_char1\"\/><\/jats:private-char>(<jats:italic>n,r<\/jats:italic>): if <jats:italic>r<\/jats:italic> \u2264 <jats:italic>K<\/jats:italic><jats:sub>3<\/jats:sub> log <jats:italic>n<\/jats:italic>\/<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000338_char2\"\/><\/jats:private-char> then <jats:italic>c<\/jats:italic>(<jats:italic>G<\/jats:italic>) &gt; 1 w.h.p., where <jats:italic>K<\/jats:italic><jats:sub>3<\/jats:sub> &gt; 0 is an absolute constant.<\/jats:p>","DOI":"10.1017\/s0963548312000338","type":"journal-article","created":{"date-parts":[[2012,8,16]],"date-time":"2012-08-16T12:15:43Z","timestamp":1345119343000},"page":"816-834","source":"Crossref","is-referenced-by-count":10,"title":["Cops and Robbers on Geometric Graphs"],"prefix":"10.1017","volume":"21","author":[{"given":"ANDREW","family":"BEVERIDGE","sequence":"first","affiliation":[]},{"given":"ANDRZEJ","family":"DUDEK","sequence":"additional","affiliation":[]},{"given":"ALAN","family":"FRIEZE","sequence":"additional","affiliation":[]},{"given":"TOBIAS","family":"M\u00dcLLER","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2012,8,16]]},"reference":[{"key":"S0963548312000338_ref17","first-page":"163","article-title":"Cops, robbers and graphs","volume":"36","author":"Hahn","year":"2007","journal-title":"Tatra Mountain Math. Publ."},{"key":"S0963548312000338_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20591"},{"key":"S0963548312000338_ref30","unstructured":"Pra\u0142at P. and Wormald N. Meyniel's conjecture holds in random graphs. Submitted."},{"key":"S0963548312000338_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579201"},{"key":"S0963548312000338_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90033-3"},{"key":"S0963548312000338_ref9","doi-asserted-by":"publisher","DOI":"10.1090\/stml\/061"},{"key":"S0963548312000338_ref19","volume-title":"Poisson Processes","author":"Kingman","year":"1993"},{"key":"S0963548312000338_ref7","unstructured":"Bollob\u00e1s B. , Kun G. and Leader I. Cops and robbers in random graphs. Submitted."},{"key":"S0963548312000338_ref10","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2007.10129149"},{"key":"S0963548312000338_ref2","unstructured":"Alon N. (2011) Personal communication."},{"key":"S0963548312000338_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(97)00165-9"},{"key":"S0963548312000338_ref6","first-page":"2054","volume-title":"Proc. Twenty-Second International Joint Conference on Artificial Intelligence","author":"Bhadauria","year":"2011"},{"key":"S0963548312000338_ref5","unstructured":"Baird W. and Bonato A. Meyniel's conjecture on the cop number: A survey. Submitted."},{"key":"S0963548312000338_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20320"},{"key":"S0963548312000338_ref15","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195999000273"},{"key":"S0963548312000338_ref31","unstructured":"Quilliot A. (1978) Jeux et pointes fixes sur les graphes. PhD thesis, Universit\u00e9 de Paris VI."},{"key":"S0963548312000338_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90160-7"},{"key":"S0963548312000338_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90073-8"},{"key":"S0963548312000338_ref21","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1997.620123"},{"key":"S0963548312000338_ref3","first-page":"5","article-title":"Sweeping and searching in graphs: A brief survey","volume":"59","author":"Alspach","year":"2006","journal-title":"Mathematiche"},{"key":"S0963548312000338_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1784-8_33"},{"key":"S0963548312000338_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.065"},{"key":"S0963548312000338_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.04.012"},{"key":"S0963548312000338_ref22","article-title":"On Meyniel's conjecture of the cop number","author":"Lu","year":"2011","journal-title":"J. Graph Theory"},{"key":"S0963548312000338_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2010.10.002"},{"key":"S0963548312000338_ref28","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"S0963548312000338_ref29","first-page":"285","article-title":"When does a random graph have constant cop number?","volume":"46","author":"Pra\u0142at","year":"2010","journal-title":"Australasian J. Combin."},{"key":"S0963548312000338_ref32","doi-asserted-by":"publisher","DOI":"10.1137\/100812963"},{"key":"S0963548312000338_ref34","volume-title":"Foundations and Trends in Networking","author":"Xue","year":"2006"},{"key":"S0963548312000338_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2012.02.018"},{"key":"S0963548312000338_ref18","first-page":"864","article-title":"Randomized pursuit-evasion in a polygonal environment","volume":"5","author":"Isler","year":"2005","journal-title":"IEEE Trans. Robotics"},{"key":"S0963548312000338_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00411-4"},{"key":"S0963548312000338_ref23","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20338"},{"key":"S0963548312000338_ref27","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1214\/aoap\/1034625335","article-title":"The longest edge of the random minimal spanning tree","volume":"7","author":"Penrose","year":"1997","journal-title":"Ann. Appl. Probab."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548312000338","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T21:59:43Z","timestamp":1556143183000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548312000338\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,16]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2012,11]]}},"alternative-id":["S0963548312000338"],"URL":"https:\/\/doi.org\/10.1017\/s0963548312000338","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,16]]}}}