{"entities":{"Q793755":{"pageid":795603,"ns":120,"title":"Item:Q793755","lastrevid":64460883,"modified":"2026-04-11T20:01:35Z","type":"item","id":"Q793755","labels":{"en":{"language":"en","value":"A game of cops and robbers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3857163"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793755$D5B30650-EB82-47C8-A644-A53847CB1413","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d37aaf76faf542e15eeff68f5fdee3133a4a54cc","datavalue":{"value":{"text":"A game of cops and robbers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q793755$0426F839-EB05-42D8-AB9D-2C8846A3DA12","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0d2d9139f0d0e1d4a0e75bf8d0245e3ee8edbe3f","datavalue":{"value":"0539.05052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793755$59F4BB88-4F53-4B2F-BA66-E07B7BA59453","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0e133dbb31b0f0b377400c9b3307696f8061c699","datavalue":{"value":"10.1016/0166-218X(84)90073-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793755$EAFF6070-21B0-4B79-92AF-6F58E899EA3A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"289d49a761dfac02c62be4b7f68381ebc5e52ce3","datavalue":{"value":{"entity-type":"item","numeric-id":495333,"id":"Q495333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793755$CD31E162-408B-4653-B9EA-14E14F482BE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bc362784070de13f1e4e13c634ab5e6aa3d29c0f","datavalue":{"value":{"entity-type":"item","numeric-id":793754,"id":"Q793754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793755$A7869017-3B7A-46AF-966F-2F516F7A60E6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793755$51BBAA4B-1B19-412E-A2C9-9BA745260389","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q793755$F9E28BED-0E8C-4EFA-9659-1A74671AE378","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"153666149489cbff749c20e989b2ca74f16dc5da","datavalue":{"value":"Let G be a finite connected undirected graph. Two players, the cop C and robber R, play a game on G according to the following rules. First C then R occupy some vertex of G. After that they move alternately along edges of G. The cop wins if he succeeds in eventually occupying the same vertex as R, otherwise R wins. A graph G is ''cop-win'' if C has a winning strategy; otherwise it is ''robber-win''. \\textit{R. Novakowski} and \\textit{P. Winkler} [Discrete Math. 43, 235-239 (1983; Zbl 0508.05058)] previously gave an algorithmic characterization of cop-win graphs, and showed that this family formed a ''variety'' in the sense of closure under (strong) graph products and retractions. The Novakowski-Winkler results are first reviewed, and then the authors generalize the game to a game where a team of n cops chase the robber. The ''cop number'' c(G) is defined to be the minimum number of cops required to catch the robber in G. Graphs \\(G_ n\\) are constructed for which \\(c(G_ n)\\geq n\\), namely n-regular graphs with girth at least 5. The most striking result proved is that c(G)\\(\\leq 3\\) for all planar graphs G.","type":"string"},"datatype":"string"},"type":"statement","id":"Q793755$29A8D820-120B-480B-89FE-291D3A52090B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1be7cda1f2fda1d13448035bf1c8e3fcef0c4ff8","datavalue":{"value":"05C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793755$D19C9EF7-0967-4E4D-A4CC-9955C1D835B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793755$CD2E7BDA-3A86-4850-94A8-5D77BF9C78C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5fbd0918ba2c4a1aeddd30d9d3d146d9773f1239","datavalue":{"value":"91A24","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793755$B7D2A2CF-116D-4002-847B-C74295E49E68","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7613f3c47e41ca97ea4f12476dc8d69ea4174efa","datavalue":{"value":"3857163","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793755$0E3B6073-5B2B-4166-93F8-7054B0C04732","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0df7df2c17647ef1e20d647961a16a12a9418603","datavalue":{"value":"game on graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q793755$8F2C721C-C3E1-4E4B-9203-7D1FC16E8BC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c378ce4bd65c154ec11811b2747355486da1e57","datavalue":{"value":"cop number","type":"string"},"datatype":"string"},"type":"statement","id":"Q793755$B0919374-8E29-4E74-B8D5-C21CB4AE56A1","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793755$1C152335-22E8-4E8F-A594-949F14D7B8AC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793755$5B1D2204-8D8A-4335-81F8-3929E73EB367","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2331ce68ffb229fed2b483ef84f522a367994688","datavalue":{"value":{"entity-type":"item","numeric-id":1838985,"id":"Q1838985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793755$17EF1B37-4B57-4A81-ACAC-02E714CFDA2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcd7542caac5915c8f63a224b76605abf20c2235","datavalue":{"value":{"entity-type":"item","numeric-id":1837707,"id":"Q1837707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793755$3D349E2C-E2DD-44C8-AEE0-10F90837687D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1aec7a5195d839105a9eaed2e0df2aa8b7b1aebe","datavalue":{"value":{"entity-type":"item","numeric-id":4159394,"id":"Q4159394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793755$6CACBBB3-3C4B-4EE7-9E19-9874245170FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e235b1e856f674628ea45299d84fda7e204eaef1","datavalue":{"value":{"entity-type":"item","numeric-id":3208679,"id":"Q3208679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793755$AC9E8C90-552E-4914-AA92-A1FF3FC7FBDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c5b5c1678e352f8b26f85ccb333a96eeabb57d7","datavalue":{"value":{"entity-type":"item","numeric-id":1821043,"id":"Q1821043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793755$874676C8-EA28-4D74-8B7F-0F2BFBD54F07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c2db494c199f19d1fe9ad0f5e20b55b7cc0401c","datavalue":{"value":{"entity-type":"item","numeric-id":5516556,"id":"Q5516556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793755$37306FCA-2296-4C83-99FB-A855EDE1881E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"06d71db888b79605250e15768d0b4c77b28d254e","datavalue":{"value":"https://doi.org/10.1016/0166-218x(84)90073-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q793755$BE8A3121-3D34-4227-8949-1FCF4E3DF663","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0e5464155e13cb5b8fc92ed3adf1c2f9b12d61b5","datavalue":{"value":"W2046635105","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793755$517362E4-53F4-4CD3-B161-EA6EA849B5C6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"515e9d59d5ad7327a1b5ed0c9a853b9609de4e4b","datavalue":{"value":{"entity-type":"item","numeric-id":5445040,"id":"Q5445040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a116a8bebdbcb7a85b322c43f4cc6b2a3f09849","datavalue":{"value":{"amount":"+0.910458505153656","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q793755$AA300F30-3052-4936-967D-E8CF5EA3E8F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6851df09b806eb5eb8513d6eb1ff675894e9cdc1","datavalue":{"value":{"entity-type":"item","numeric-id":799702,"id":"Q799702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f9c31f34d61dd5656480cf266bb181626e1e6dc","datavalue":{"value":{"amount":"+0.8970904350280762","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q793755$F211E3E3-F672-4716-9EB5-41E8C7B2A6BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e9293f6ddfa7b9fd2e7c58dee44afed3f1aeab6","datavalue":{"value":{"entity-type":"item","numeric-id":3798505,"id":"Q3798505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2eb8c40c06740ef31842878d514d3bb53015b8f4","datavalue":{"value":{"amount":"+0.894524335861206","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q793755$43EC5050-9D54-4E36-9E1A-4DFF11DD98ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7df5fb809c9b967f0a126d940f30f0c722b01e86","datavalue":{"value":{"entity-type":"item","numeric-id":4596319,"id":"Q4596319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b34db46c2ff1637e47a6e0491da87beb86b7ab2f","datavalue":{"value":{"amount":"+0.8928150534629822","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q793755$CF42490B-EE50-421B-9E7E-D5AB0701C24F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2086b13f6a1f22f9695513e1953c723932a7a7ed","datavalue":{"value":{"entity-type":"item","numeric-id":1325748,"id":"Q1325748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"294d7c9e7480cc6f74efbcae56b35ef58243efc7","datavalue":{"value":{"amount":"+0.8881276249885559","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q793755$8B438316-F0FB-4E2A-AA8C-574D7D410B62","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A game of cops and robbers","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_game_of_cops_and_robbers"}}}}}