{"entities":{"Q1025953":{"pageid":1027801,"ns":120,"title":"Item:Q1025953","lastrevid":66652671,"modified":"2026-04-12T11:34:27Z","type":"item","id":"Q1025953","labels":{"en":{"language":"en","value":"A witness version of the cops and robber game"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5569075"}},"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":"Q1025953$53B0CA1E-34EA-48DE-8178-AEDBB51FE238","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"239549130468076c98afd05c0362555c73bd5724","datavalue":{"value":{"text":"A witness version of the cops and robber game","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1025953$3415D7BE-0D3F-4CB0-AF96-B85276E06355","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b72b33facd9f3bc540b760717022bd6a6476645c","datavalue":{"value":"1167.91004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1025953$90DDF4A2-916D-4A34-AAF8-581BD5891B04","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"28d9a11755063406133e4636326065a76695e284","datavalue":{"value":{"entity-type":"item","numeric-id":244920,"id":"Q244920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025953$17E50213-2E06-4701-BFBC-4CB9A75D1E20","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025953$49AA043D-A533-4172-BDC4-39EE7A9AEC70","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f66a2f08b182488ffaf8c1a4c74cdffeb2d3409b","datavalue":{"value":{"time":"+2009-06-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1025953$2839B99D-164E-468A-986F-9C267364143E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c2d9a68f49cce148b290c17f96df87c4af7ad13b","datavalue":{"value":"In the usual game of cops and robbers, played on a graph with a loop at each vertex, there are \\(k>0\\) cops and a single robber. To begin, each of the cops chooses a vertex and then the robber chooses a vertex. The sides move alternately, a move consisting of moving along an edge to an adjacent vertex (possibly the same one, via a loop). Both sides have perfect information, and the cops win if at some time the robber and one of the cops occupy the same vertex. A graph on which a single cop can always win is called a copwin. In this paper a variation of this game is studied in which the robber still has perfect information but the cops do not. They receive information intermittently from witnesses who report sightings of the robber. This information may come at regular intervals, every \\(k\\) units of time (the \\(k\\)-regular case), or may come sporadically. A graph on which a single cop can win with sightings every \\(k\\) units of time is called \\(k\\)-winnable. Some results are obtained for irregular information games, but the bulk of the paper is devoted to \\(k\\)-regular games. An example is given of a copwin graph that is not \\(k\\)-winnable for any \\(k\\), and several theorems are obtained for \\(k\\)-regular games. Special attention is paid to triangle-free \\(k\\)-winnable graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1025953$684DFD80-A84E-4B95-A6B5-B5AE7C4BB371","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6cd669872d281c67042af939aa0a07de1efaf0d9","datavalue":{"value":{"entity-type":"item","numeric-id":227634,"id":"Q227634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025953$63AAA47E-B5F0-4F5E-8CC5-ECEFE612DCAE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b98cb7058a1e8e644c33a49a426b651c0e594493","datavalue":{"value":"91A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1025953$67171514-9A9F-4E07-83F8-37CEFAD2DEF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1025953$C878C825-EBD3-4B1C-B96F-39293FCABBD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a7dd7003e1269b5b10ff3f935da8af9e44f172f","datavalue":{"value":"91A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1025953$2942B4CF-3C2B-423D-A94E-02851AFDF8B0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c668480a5d597ea1f77521d996e3525a75cc8a10","datavalue":{"value":"5569075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1025953$9503714C-F64B-4A92-91A8-DACD1EB29187","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4bbfcd025527bef4af04ed2382b13f4d77d7e37c","datavalue":{"value":"cop","type":"string"},"datatype":"string"},"type":"statement","id":"Q1025953$70FE1BCD-FA93-46E7-8274-476C7D41CE25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e20402354069a8eb017132b31d371122d76e96c","datavalue":{"value":"partial information","type":"string"},"datatype":"string"},"type":"statement","id":"Q1025953$E783EAED-8A1B-400B-B179-627CBDABF86A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3336b0518162d61ed57d02a0de4e9d8d061f3981","datavalue":{"value":"witness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1025953$0CBEFA1E-F8C4-451A-98E9-C6A706EF3D43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d172646b9b6d6f2fd3e08b25017dd7cbd525a4a8","datavalue":{"value":"pursuit","type":"string"},"datatype":"string"},"type":"statement","id":"Q1025953$F4CD5ED7-1438-4751-9EDB-A3C92F1EF743","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6144280334559a6115bb843e62e7394a2e844ae4","datavalue":{"value":"structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1025953$336CC6E9-B864-47D8-9DB3-D3B1A4D42F8A","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":"Q1025953$7DF3F2D0-E493-497D-B9AD-40B5752E21F3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1d3bc02893d8ed7b7244272b3189fd2d43f0680f","datavalue":{"value":"https://doi.org/10.1016/j.disc.2008.09.032","type":"string"},"datatype":"url"},"type":"statement","id":"Q1025953$BE71B2CF-952E-4440-85A6-0F84324FFFEF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b78dcaf4a97eb44eb046821b663b8217d3084f8d","datavalue":{"value":"W1992555158","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1025953$2014630E-E7C3-4F5A-8FA7-3AF17D9E0108","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"de271bc98faea784dba49f7dbe2a8ec41708fa09","datavalue":{"value":{"entity-type":"item","numeric-id":3418339,"id":"Q3418339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025953$F1828F72-B6E9-4629-8CDA-91677297DBC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"282d88b529308441c287f6c692de7afeae122bdc","datavalue":{"value":{"entity-type":"item","numeric-id":4243764,"id":"Q4243764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025953$3D1FB5EB-EFAA-4F2D-BBF4-30747B4E24EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"275e2b71f4636e5a9d205801dd18be70d6563bbb","datavalue":{"value":{"entity-type":"item","numeric-id":4210215,"id":"Q4210215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025953$A7CD839C-A896-412E-A149-6EA12ECA405A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d432054fc05f862ce9b410e3f94ba3c84709623","datavalue":{"value":{"entity-type":"item","numeric-id":5310227,"id":"Q5310227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025953$A16FBADA-9CA7-452F-AC38-3CBF96D1293B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"292060ec5dde7259d7b947b4906befb8b8ff6cce","datavalue":{"value":{"entity-type":"item","numeric-id":2568474,"id":"Q2568474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025953$EB8BA000-8146-4A07-865F-F751C873C47E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f62e5c3f1349aeec4ab8f662d9c628cdd928a718","datavalue":{"value":{"entity-type":"item","numeric-id":4677834,"id":"Q4677834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025953$ED125A43-A09A-45B7-8876-76AD9965E6C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fcf811c25b16e0e7c7ed8be72a19e024a5b75ba","datavalue":{"value":{"entity-type":"item","numeric-id":4552216,"id":"Q4552216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025953$588B7491-372F-4C38-AF54-9B4F940E3B26","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":"Q1025953$75B00EBB-BAD2-49F2-B1FD-5137C4532F7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87ecca2ff62f641884d2d9a89d1b8049fca4b34d","datavalue":{"value":{"entity-type":"item","numeric-id":1072462,"id":"Q1072462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1025953$CCFCEEFD-3880-439E-BFFB-A3A88F29C607","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"89e4ad945825d70758eb38e5e9b06590320000ac","datavalue":{"value":"10.1016/J.DISC.2008.09.032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1025953$DCC4EB05-6CA0-4FDF-B154-85DD7D292CCD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9ea4e7c32ada25f0e74b833e78a04b7e6a806e5","datavalue":{"value":{"entity-type":"item","numeric-id":5310227,"id":"Q5310227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbdd2d34c25a30d3b6d6ed5693440024eab9af18","datavalue":{"value":{"amount":"+0.8874691724777222","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":"Q1025953$C545A917-0F5C-4179-ADD5-7DA5E25FE51F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5195a7dc0357ecda41043df911c0ddd82e6dc37a","datavalue":{"value":{"entity-type":"item","numeric-id":3508551,"id":"Q3508551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03bf7f2c40354a5f362b8be6297d72ee4a60d11a","datavalue":{"value":{"amount":"+0.8873997330665588","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":"Q1025953$78CACB82-F1F1-435D-AC63-E5266A935209","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40ea45c9d955f3e829e6fb4f5219059f258d1402","datavalue":{"value":{"entity-type":"item","numeric-id":4677834,"id":"Q4677834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b983ad33470776159d85e5300ff9bca0b36b6918","datavalue":{"value":{"amount":"+0.8449407815933228","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":"Q1025953$F1161608-0630-451E-8368-461A8322D788","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b56d1723343aaba9e81d819bb34e2ec31519199","datavalue":{"value":{"entity-type":"item","numeric-id":930890,"id":"Q930890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7019a9f45a65fc5243b593943e9118df13a0e75b","datavalue":{"value":{"amount":"+0.8420170545578003","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":"Q1025953$32BF40D4-DE4E-49C6-B7B0-262D81496312","rank":"normal"},{"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":"fc4bf820b5280350b619d349b0ca113a1837231b","datavalue":{"value":{"amount":"+0.8125841021537781","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":"Q1025953$350D07FE-ABCA-43C8-B587-606915C2A05A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A witness version of the cops and robber game","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_witness_version_of_the_cops_and_robber_game"}}}}}