{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,5,3]],"date-time":"2022-05-03T15:34:48Z","timestamp":1651592088496},"reference-count":17,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2013,3,8]],"date-time":"2013-03-08T00:00:00Z","timestamp":1362700800000},"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":[[2013,5]]},"abstract":"<jats:p>Pursuit-evasion games, such as the game of Revolutionaries and Spies, are a simplified model for network security. In the game we consider in this paper, a team of <jats:italic>r<\/jats:italic> revolutionaries tries to hold an unguarded meeting consisting of <jats:italic>m<\/jats:italic> revolutionaries. A team of <jats:italic>s<\/jats:italic> spies wants to prevent this forever. For given <jats:italic>r<\/jats:italic> and <jats:italic>m<\/jats:italic>, the minimum number of spies required to win on a graph <jats:italic>G<\/jats:italic> is the spy number \u03c3(<jats:italic>G,r,m<\/jats:italic>). We present asymptotic results for the game played on random graphs <jats:italic>G(n,p)<\/jats:italic> for a large range of <jats:italic>p = p(n)<\/jats:italic>, <jats:italic>r=r(n)<\/jats:italic>, and <jats:italic>m=m(n)<\/jats:italic>. The behaviour of the spy number is analysed completely for dense graphs (that is, graphs with average degree at least <jats:italic>n<\/jats:italic><jats:sup>1\/2+\u03b5<\/jats:sup> for some \u03b5 &gt; 0). For sparser graphs, some bounds are provided.<\/jats:p>","DOI":"10.1017\/s0963548313000072","type":"journal-article","created":{"date-parts":[[2013,3,8]],"date-time":"2013-03-08T14:24:37Z","timestamp":1362752677000},"page":"417-432","source":"Crossref","is-referenced-by-count":1,"title":["Revolutionaries and Spies on Random Graphs"],"prefix":"10.1017","volume":"22","author":[{"given":"DIETER","family":"MITSCHE","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PAWE\u0141","family":"PRA\u0141AT","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2013,3,8]]},"reference":[{"key":"S0963548313000072_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90160-7"},{"key":"S0963548313000072_ref12","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20338"},{"key":"S0963548313000072_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548313000072_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.02.040"},{"key":"S0963548313000072_ref3","doi-asserted-by":"publisher","DOI":"10.1090\/stml\/061"},{"key":"S0963548313000072_ref1","doi-asserted-by":"crossref","DOI":"10.1201\/b10691","volume-title":"Lessons in Play","author":"Albert","year":"2007"},{"key":"S0963548313000072_ref14","first-page":"285","article-title":"When does a random graph have constant cop number?","volume":"46","author":"Pra\u0142at","year":"2010","journal-title":"Australas. J. Combin."},{"key":"S0963548313000072_ref2","first-page":"5","article-title":"Sweeping and searching in graphs: A brief survey.","volume":"59","author":"Alspach","year":"2006","journal-title":"Matematiche"},{"key":"S0963548313000072_ref5","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2007.10129149"},{"key":"S0963548313000072_ref9","first-page":"163","article-title":"Cops, robbers and graphs.","volume":"36","author":"Hahn","year":"2007","journal-title":"Tatra Mt Math. Publ."},{"key":"S0963548313000072_ref17","volume-title":"Jeux et pointes fixes sur les graphes","author":"Quilliot","year":"1978"},{"key":"S0963548313000072_ref15","unstructured":"Pra\u0142at P. and Wormald N. Meyniel's conjecture holds for random graphs. Preprint."},{"key":"S0963548313000072_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.10.002"},{"key":"S0963548313000072_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.05.041"},{"key":"S0963548313000072_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2012.08.001"},{"key":"S0963548313000072_ref7","doi-asserted-by":"publisher","DOI":"10.4310\/JOC.2012.v3.n2.a4"},{"key":"S0963548313000072_ref16","unstructured":"Pra\u0142at P. and Wormald N. Meyniel's conjecture holds for random d-regular graphs. Preprint."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548313000072","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,23]],"date-time":"2019-04-23T22:01:13Z","timestamp":1556056873000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548313000072\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3,8]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["S0963548313000072"],"URL":"https:\/\/doi.org\/10.1017\/s0963548313000072","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3,8]]}}}