{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,20]],"date-time":"2023-08-20T04:39:31Z","timestamp":1692506371892},"reference-count":23,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2022,6,28]],"date-time":"2022-06-28T00:00:00Z","timestamp":1656374400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2023,1]]},"abstract":"Abstract<\/jats:title>We establish a lower bound for the cop number of graphs of high girth in terms of the minimum degree, and more generally, in terms of a certain growth condition. We show, in particular, that the cop number of any graph with girth and minimum degree is at least . We establish similar results for directed graphs. While exposing several reasons for conjecturing that the exponent in this lower bound cannot be improved to , we are also able to prove that it cannot be increased beyond . This is established by considering a certain family of Ramanujan graphs. In our proof of this bound, we also show that the \u201cweak\u201d Meyniel's conjecture holds for expander graph families of bounded degree.<\/jats:p>","DOI":"10.1002\/jgt.22855","type":"journal-article","created":{"date-parts":[[2022,6,28]],"date-time":"2022-06-28T07:27:28Z","timestamp":1656401248000},"page":"15-34","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the cop number of graphs of high girth"],"prefix":"10.1002","volume":"102","author":[{"ORCID":"http:\/\/orcid.org\/0000-0003-2562-6141","authenticated-orcid":false,"given":"Peter","family":"Bradshaw","sequence":"first","affiliation":[{"name":"Department of Mathematics Simon Fraser University Burnaby Canada"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-6775-5665","authenticated-orcid":false,"given":"Seyyed Aliasghar","family":"Hosseini","sequence":"additional","affiliation":[{"name":"Department of Mathematics Simon Fraser University Burnaby Canada"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-7408-6148","authenticated-orcid":false,"given":"Bojan","family":"Mohar","sequence":"additional","affiliation":[{"name":"Department of Mathematics Simon Fraser University Burnaby Canada"}]},{"given":"Ladislav","family":"Stacho","sequence":"additional","affiliation":[{"name":"Department of Mathematics Simon Fraser University Burnaby Canada"}]}],"member":"311","published-online":{"date-parts":[[2022,6,28]]},"reference":[{"key":"e_1_2_7_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90073-8"},{"key":"e_1_2_7_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90026-2"},{"issue":"2","key":"e_1_2_7_4_1","first-page":"225","article-title":"Meyniel's conjecture on the cop number: A survey","volume":"3","author":"Baird W.","year":"2012","journal-title":"J. Comb."},{"key":"e_1_2_7_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.10.002"},{"key":"e_1_2_7_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10023"},{"issue":"3","key":"e_1_2_7_7_1","first-page":"507","article-title":"Bounding the cop number of a graph by its genus","volume":"88","author":"Bowler N.","year":"2019","journal-title":"Acta Math. Univ. Comenian. (N.S.)"},{"key":"e_1_2_7_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2021.103383"},{"key":"e_1_2_7_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90033-3"},{"key":"e_1_2_7_10_1","doi-asserted-by":"crossref","unstructured":"F.HasiriandI.Shinkar Meyniel extremal families of Abelian Cayley graphs Graphs Comb.38(2022). no. 3.https:\/\/doi.org\/10.1007\/s00373-022-02460-8","DOI":"10.1007\/s00373-022-02460-8"},{"key":"e_1_2_7_11_1","unstructured":"S. A.Hosseini \u00a0Game of cops and robbers on Eulerian digraphs Ph.D. thesis Simon Fraser University \u00a02018."},{"key":"e_1_2_7_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2021.06.008"},{"key":"e_1_2_7_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20642"},{"key":"e_1_2_7_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"e_1_2_7_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20338"},{"key":"e_1_2_7_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(89)90029-4"},{"key":"e_1_2_7_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04016-0"},{"key":"e_1_2_7_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90160-7"},{"key":"e_1_2_7_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20587"},{"key":"e_1_2_7_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20874"},{"key":"e_1_2_7_21_1","unstructured":"A.Quilliot \u00a0Probl\u00e8mes de jeux de point fixe de connectivit\u00e9 et de repr\u00e9sentation sur des graphes des ensembles ordonn\u00e9s et des hypergraphes Ph.D. thesis Universit\u00e9 de Paris VI \u00a01978."},{"key":"e_1_2_7_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1370-3_14"},{"key":"e_1_2_7_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/100812963"},{"key":"e_1_2_7_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0605030"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.22855","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/jgt.22855","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.22855","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,19]],"date-time":"2023-08-19T14:02:48Z","timestamp":1692453768000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.22855"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,28]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["10.1002\/jgt.22855"],"URL":"https:\/\/doi.org\/10.1002\/jgt.22855","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,28]]},"assertion":[{"value":"2021-11-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-21","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}